-2
$\begingroup$

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)

enter image description here

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

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

Improve this question
$\endgroup$
4
  • $\begingroup$ 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)$, $\endgroup$
    – Steven
    Nov 19 at 18:46
  • $\begingroup$ 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)$? $\endgroup$
    – tbhaxor
    Nov 19 at 18:50
  • 3
    $\begingroup$ 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. $\endgroup$
    – mrk
    Nov 19 at 19:14
  • $\begingroup$ @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. $\endgroup$
    – Steven
    Nov 19 at 22:33

1 Answer 1

Reset to default
0
$\begingroup$

Time complexities often have context; it can be average, best, or worst. For example, searching for an element in a non-sorted array would require O(1) time if you go from left to right and the leftmost element is the one you were searching for. However, if it was the last element, it would take O(n) time. Therefore, we say the worst-case time complexity is O(n)( providing an intuitive definition for certain cases)

Amortized time complexity, (for a formal definition check the potential method or amortized cost analysis in general), considers the time complexity over n operations and takes the average of it informally. The problem of calculating time complexity in your question is similar to calculating the dynamic array implementation using a static array. You can check that it is O(1) amortized using that resizing mechanism. I would like to suggest watching the following lecture on dynamic arrays: https://www.youtube.com/watch?v=CHhwJjR0mZA

Improve this answer
$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.