# Why the time for push operation in doubled growth stack is $O(n)$, not $O(\log{n})$? [closed]

I am learning the dynamic stack implementation using 2 ways (incremental and double)

When stack is full, then only it will grow 2x of capacity

stack->storage = realloc(stack, stack->capacity * 2 * sizeof(int));
stack->capacity *= 2;


So the for $$n$$ elements, the stack will be grown $$\log_2{n}$$ times (times the realloc is called). And the copy operation on old elements only happens on the growth.

The calculation is not clear to me (Page 97, Data Structures and Algorithm made easy)

Based on the geometric progression, shouldnt it $$𝑂(2^𝑛)$$?

Here I am assuming for every realloc, we will get a different memory location.

• Can you clarify what you are asking? The worst-case time for a single push $O(n)$ since realloc needs to copy the whole old array into the new one. The overall time spent reallocating the array for a sequence of $n$ push operations is (roughly) given by the image you posted..., since the rest of the time is $O(1)$ per push, the overall time to handle $n$ pushes is $O(n)$, Nov 19 at 18:46
• Yes, why it is O(n), that is where I am currently stuck. Also if we are taking that into consideration, then it should be $O(2^n)$? Nov 19 at 18:50
• You are right but you got confused by the $n$. The number of calls is $log_2 n$ so $O(2^{log_2 n})$ which is $O(n)$ if you simplify.
– mrk
Nov 19 at 19:14
• @tbhaxor What is the "it" you're talking about when you say "why it is O(n)"? Is it the worst-case time complexity of a single push operation, or the overall time complexity of $n$ push operations? Also, since both of these times are in $O(n)$ they are clearly also in $O(2^n)$ but that's a gross overestimation. Nov 19 at 22:33