Space complexity of vector push_back

Question

I have code that is first creating a vector (vector B). My code then loops through a different vector (vector A) in the program and adds that index to the back of Vector B.

My thoughts are that since we are looping through n elements the time complexity will be worse case O(n^2) since we might need to create an entirely new array if vector b gets too big. average time of O(n) since push back usually is constant.

Now for space complexity since we are already creating space to hold n elements, it would be O(N). However, if our vector is too big we might need to create an entirely new one of O(N) size. So would our space be O(2n) which is just O(n) or would it be O(n + m) (m being the size of the new array).

Thanks!

Unrelated: Your time complexity is incorrect. `push_back` is [amortized O(1) time complexity](https://stackoverflow.com/questions/200384/constant-amortized-time). There is normally extra space and no extra work, the item is inserted in one iteration. When extra space is required, there may be an O(N) copy loop, not O(N^2). — user4581301, May 09 '19 at 23:01
So we are in a loop of n already, and when we try to push_back when full it may need n time to copy elements, so why wouldn't we multiply the operations inside the for loop by the time of the for loop? giving us n^2 — wallischpls, May 09 '19 at 23:10
There is no loop of n. The `vector` knows exactly where the end is and can insert directly (O(1)). No searching required. Even if it did have to search, that would be O(N) for the search followed by another, completely separate O(N) to copy to the new allocation, and 2 O(N)s is still O(N). O(N^2) would mean that for every iteration in the search loop the program would copy the entire `vector`. — user4581301, May 09 '19 at 23:17
O(1) means you visit exactly one element no matter how big N is. O(N) means you visit each of N elements a constant amount of times. O(N^2) means you visit each of N elements N (possibly times a constant) times. What this means to you is if you double N with O(1), you do the same amount of work. If you double N with O(N), you double the work. With O(N^2) if you double N you quadruple the work. — user4581301, May 09 '19 at 23:23
Possibly of interest: https://stackoverflow.com/a/5232342/131930 — Jeremy Friesner, May 10 '19 at 01:06

eerorika · Answer 1 · 2019-05-10T01:10:55.233

Concerning time complexity:

Worst case of a single push back is linear (unless memory is pre-reserved in which case worst case is constant as long as the size doesn't grow beyond the reserved size). Average case is constant.

Both worst and average case of N push back total is linear, whether memory has been reserved or not.

So would our space be O(2n) which is just O(n) or would it be O(n + m) (m being the size of the new array).

It doesn't really matter asymptotically. The new size is a constant multiple (c) of the old size, so O(n + m) -> O(n + (n * c)) -> O ((c + 1) * n) -> O(n). So, the complexity is the same either way.

Space complexity of vector push_back

1 Answers1