[jemfinch]

You're forgetting that half the array is never copied. The total number of copies doesn't exceed a linear cN, so it's O(N), not O(N log(N)).

The constant bound on the number of copies depends on the growth factor. With a growth factor of 2, the constant is 2. As long as the growth factor is greater than 1, the number of copies is linear.

You can verify this yourself with some trivial code:

    struct CountsCopies {
      CountsCopies() {}
      CountsCopies(const CountsCopies& other) { ++CopyCount(); }
      CountsCopies& operator=(const CountsCopies& other) { ++CopyCount(); return *this; }
      static std::size_t& CopyCount() {
        static std::size_t count = 0;
        return count;
      }
    };

    std::size_t last_copies = 0;
    std::vector<CountsCopies> v;
    for (int i = 0; i < 1000; ++i) {
      const std::size_t copies = CountsCopies::CopyCount();
      if (copies != last_copies) {
        std::cout << "size=" << i << " copies=" << copies
                  << " ratio=" << copies / static_cast<double>(i) << '\n';
        last_copies = copies;
      }
      v.emplace_back();
    }

Output:

    size=2 copies=1 ratio=0.5
    size=3 copies=3 ratio=1
    size=5 copies=7 ratio=1.4
    size=9 copies=15 ratio=1.66667
    size=17 copies=31 ratio=1.82353
    size=33 copies=63 ratio=1.90909
    size=65 copies=127 ratio=1.95385
    size=129 copies=255 ratio=1.97674
    size=257 copies=511 ratio=1.98833
    size=513 copies=1023 ratio=1.99415