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() &amp;&amp; X[A.top()] &lt;= X[i] ) do
            A.pop()
        if A.isEmpty() then
            S[i] = i + 1
        else
            S[i] = i - A.top()
        A.push(i)
    return S
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.