How is the asymptotic complexity of finding the Next Greater Element's linear time?

Question

I was reading an algorithm to get the Next Greater Element for each element of an array.

The site claims that their code runs in O(n) time, but I am not able to wrap my head around it.

A complete traversal of the array from left to right will itself cost O(n), on top of which there can be multiple push / pop operations at each index as we traverse the list.

Although the push / pop operations take constant time, if they are called on an average say m times per index element, we would have O(m) as the cost of push / pop operations at each index, leading to O(mn) as the total cost, now since the total number of push / pop operations should be approximately (or maybe exactly) equal to the n, we can say that mn is approximately (or maybe exactly) equal to n implying that m is a constant.

Is my justification right?

I still don't have proper clarity with my own reasoning, could somebody provide a better explanation in addition to validating / invalidating my justification?

Answer 1

Pseudo-code copied here for convenience:

1. Push the first element to stack.
   
2. Pick rest of the elements one by one and follow following steps in loop.
   
   1. Mark the current element as next.
      
   2. If stack is not empty, then pop an element from stack and compare it with next.
      
   3. If next is greater than the popped element, then next is the next greater element for the popped element.
      
   4. Keep popping from the stack while the popped element is smaller than next. next becomes the next greater element for all such popped elements
      
   5. If next is smaller than the popped element, then push the popped element back.
      
   6. Push next onto the stack [this step is missing from the pseudo-code]
3. After the loop in step 2 is over, pop all the elements from stack and print -1 as next element for them.

The outer loop is run O(n) times.

Clearly, with the exception of the work done for popped elements not pushed back (step #4, minus the last element it handles), the rest of the loop iteration is constant time.

So any element that keeps getting popped and pushed back onto the stack will already be included in the constant time of every iteration where it gets popped and pushed back.

All that's left are the times when elements are popped and not pushed back, but clearly this can only happen once for each element, thus this accounts for, in total, O(n) running time.

Since we never duplicate items in the stack (we push each element from the array once, then we only push again after we've popped) there can't be more than n elements in the stack, so the final step takes at most O(n) time.

Thus the total running time is O(n + n + n) = O(n).

---

An alternate way of reasoning about it:

We perform a maximum of 2 push operations during each loop iteration (which there are n of).

Thus there are at most 2n push operations, and thus also at most 2n pop operations (we can't pop elements that weren't pushed).

We do a constant amount of work per push / pop operation, and we additionally do a constant amount of work per loop iteration (ignoring the work done per push / pop operation), thus the total running time is O(n + 4n) = O(n).

Answer 2

You may have m operations per iteration of n but m is still a constant and is independent of n.

The number of push/pop operations are constant for each iteration of n so they don't affect the time complexity of the algorithm.