Running time analysis of a linear algorithm seems to me quadratic

Question

I have been analyzing an algorithm for several hours in order to find out why it is expressed as $O(n)$ (I saw this solution in a PowerPoint presentation which refers to it as a linear algorithm). I see a while loop inside a for loop.

The for loop executes $n$ times.

The while loop executes "at most" $n$ times $(0, 1, 2, ..., n - 1)$ which can be represented as $n*(n+1)/2$

So, the running time formula can be $(n)*[n*(n+1)/2]$ which yields to a quadratic expression. (I have not taken into account individual statements inside the loops for simplicity).

What is wrong with my reasoning?

Algorithm spans2(X, n) S = new array of n integers A = new empty stack for i = 0 to n - 1 do while (!A.isEmpty() && X[A.top()] <= X[i] ) do A.pop() if A.isEmpty() then S[i] = i + 1 else S[i] = i - A.top() A.push(i) return S

Answer 1

Inner while loop will be executed at most $L$ times, where $L$ is number of integers that will be added to stack $A$, and it will be at most $N$ pushes to stack, because A.push(i) is called in outer for loop, so body of inner while loop (A.pop()) will be executed at most $N$ times.

Answer 2

Your analysis is too coarse; cf. also the analysis of Dijkstra's algorithm. You find $O(n^2)$ (due to saying "at most" and ignoring constant factors) which is a valid upper bound, but it is a bad one.

If you look closer, you can show an $O(n)$ upper bound; together with a trivial $\Omega(n)$ lower bound (from the for loop alone) you get $\Theta(n)$ asymptotic runtime, i.e. linear. One way to do this is to count how often every statement is executed.

Here are the relevant observations:

• Ever iteration of the for loop pushes exactly one element to the stack.
• The while loop has at most one iteration for every element ever on the stack.

Combine these observations with what you already know, write up your statement counts and obtain the result.