3 ms·

edit: oops, nvm

scatters 7y ago
No, since the early array copies are on smaller arrays they take far less than O(n) time. The total time in copies is 1 + 2 + 4 + ... + 2^m + ... 2^(floor log2 n), which equals 2^(ceil log2 n) - 1, or O(n).
jemfinch 7y ago
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
slavik81 7y ago
The number of copies required is a geometric series. With a growth factor of 2x, the number of total copies is only 2N - 1. Thus, it is O(N). It's O(N) for any geometric growth rate, but using 2x makes it easy to see, because every copy is one larger than all previous copies combined. Consider a concrete example for N=9: 1 + 2 + 4 + 8 = 7 + 8.

edit: oops, nvm

No, since the early array copies are on smaller arrays they take far less than O(n) time. The total time in copies is 1 + 2 + 4 + ... + 2^m + ... 2^(floor log2 n), which equals 2^(ceil log2 n) - 1, or O(n).

jemfinch 7y ago

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

slavik81 7y ago

The number of copies required is a geometric series. With a growth factor of 2x, the number of total copies is only 2N - 1. Thus, it is O(N). It's O(N) for any geometric growth rate, but using 2x makes it easy to see, because every copy is one larger than all previous copies combined. Consider a concrete example for N=9: 1 + 2 + 4 + 8 = 7 + 8.