Analyzing a stack sort algorithm's time complexity
<p>I've been working through problems in Cracking the Coding Interview to prepare for some interviews. I was able to solve the stack sort problem but I'm having a really hard time figuring out how to reason about the time complexity. My solution was very similar to the one supplied in the book and I have tested it quite a bit so I'm sure it is correct. Any insight into the thought process one would go through to analyze this algorithm would be very appreciated. The book says it's O(n^2). Here is the algorithm:</p>

<pre><code>def sort_stack(stack):
    temp_stack = Stack()
    while not stack.is_empty():
        v = stack.pop()
        if temp_stack.is_empty() or temp_stack.peek() &lt;= v:
            temp_stack.push(v)
        else:
            while not temp_stack.is_empty() and temp_stack.peek() &gt; v:
                stack.push(temp_stack.pop())
            temp_stack.push(v)
    while not temp_stack.is_empty():
        stack.push(temp_stack.pop())
</code></pre>

<p>As a side note: I used this approach to sort the stack in order to be within the constraints of the problem. I am aware that faster solutions exist.</p>

<p>Thank you in advance.</p>

<p>This may be an over-simplified approach to algorithm analysis, but whenever I see a nested loop, I think n^2. Three loops nested -- n^3, etc. As a rule of thumb for simple programs, count the nested loops. This is a pretty helpful tutorial: <a href="http://cs.lmu.edu/~ray/notes/alganalysis/" rel="nofollow">http://cs.lmu.edu/~ray/notes/alganalysis/</a></p>

python algorithm sorting stack big-o