Search code examples
c++vectorbig-opush-back

Are these variants of std::vector::push_back constant or linear?

We all know that std::vector::push_back has constant (amortized) complexity. It is constant because we say that the amortization cost is negligible, doubling every time. With reallocation being linear complexity.

Let's change our std::vector interface a bit to force reallocation in different fun ways.

Reallocate at every push_back

Is push_back still O(1) (amortized) if we reallocated on every push_back?

At every push_back we go through all the items in the vector I guess the constant part would drop here and both push_back and reallocation are O(N)

Reallocate only on odd numbered push_back

Is push_back still O(1) (amortized) if we reallocate on every other push_back?

Compared to the other variant, would push_back still be linear O(N)? Or can we still assume it's constant amortized?

Solution

  • In this case, would push_back still be constant?

    No. It's O(realloc(n)), which is O(n).

    In this case, would push_back still be linear O(N)?

    Yes. It's best-case performance is O(1), it's worst case performance O(realloc(n)), which is O(n). If you call push_back N times, you will call realloc N/2 times, each using O(N), so on average we have O(N*(N/2)/N) = O(N/2) = O(N).

    Compare that to the double-the-size push_back, where on N push_back's we will only call realloc log(N) times. See this post for a detailed explanation.