CODEWITHSUNDEEP
pythonalgorithmsortingstackbig-o
rocktheartsm4l
rocktheartsm4l

Reputation: 2187

Analyzing a stack sort algorithm's time complexity

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:

def sort_stack(stack):
    temp_stack = Stack()
    while not stack.is_empty():
        v = stack.pop()
        if temp_stack.is_empty() or temp_stack.peek() <= v:
            temp_stack.push(v)
        else:
            while not temp_stack.is_empty() and temp_stack.peek() > v:
                stack.push(temp_stack.pop())
            temp_stack.push(v)
    while not temp_stack.is_empty():
        stack.push(temp_stack.pop())

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.

Thank you in advance.

Upvotes: 0

Views: 513

Answers (2)

Derek Leung
Derek Leung

Reputation: 46

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.)

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

Combining these should give O(n^2).

Upvotes: 2

denvaar
denvaar

Reputation: 2214

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: http://cs.lmu.edu/~ray/notes/alganalysis/

Upvotes: 1

Related Questions