# Running time analysis of a linear algorithm seems to me quadratic

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

• not related to time-complexity: What is purpose of this algo? Where is it used? Looks like for each element of array it's calculate closest number on the left that is bigger. – knok16 Jul 19 '15 at 23:01

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.

• Does it mean that the $A.pop()$ operation inside the $while$ is not taken into account? There is a variation of this algorithm in which $A.pop()$ is replaced with $j=A.pop()$. Is the analysis still the same? – JORGE Jul 20 '15 at 0:06
• The pop operation is actually why, over all iterations of the outer loop, the inner loop will be executed at most $L$ times in total. – Klaus Draeger Jul 20 '15 at 1:32

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.