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>Consider the worst case, in which sorting each and every item in the stack requires completely emptying the temp stack. (This happens when trying to sort a reverse-sorted stack.)</p>

<p>What is the cost of emptying/refilling the temp stack for each item?<br>
How many items are there?</p>

<p>Combining these should give O(n^2).</p>

python algorithm sorting stack big-o