Sort Stack Ascending Order (Space Analysis)

Question

I was going through the book "Cracking the Coding Interview" and came across the question "Write a program to sort a stack in ascending order. You may use additional stacks to hold items, but you may not copy the elements into any other data structures (such as an array). The stack supports the following operations: push, pop, peek, isEmpty."

The book gave an answer with O(n^2) time complexity and O(n) space.

However, I came across this blog providing an answer in O(n log n) time complexity using quicksort approach.

What I was wondering was is the space complexity O(n^2) though? Since each call to the method involves initializing another two stacks, along with another two recursive calls.

I'm still a little shaky on space complexity. I'm not sure if this would be O(n^2) space with the new stacks spawned from each recursive call being smaller than the ones a level up.

If anyone could give a little explanation behind their answer, that would be great.

Answer 1

The space complexity is also O(n log n) in average case. If space complexity happens to be O(n^2), then how can time complexity be O(n log n), as each space allocated need at least one access.

So, in average case, assuming that stack is divided in half each time, at i^th depth of recursion, size of array becomes O(n/2^{^}i) with 2^{^}i recursion branches on i^th depth.
So total size allocated on i^th depth is O(n/2^i) *2^{^}i = O(n).

Since maximum depth is log n, so overall space complexity is O(n log n).

However, in worst case, space complexity is O(n^2).

Answer 2

In this method of quicksort, the space complexity will exactly follow the time complexity - the reason is quite simple. You are dividing the sub stacks recursively (using the pivot) until each element is in a stack of size one. This leads to (2^x = n) divisions of x sub stacks (log n depth) and in the end you have n stacks each of size one. Hence the total space complexity will be O(n*log n).

Keep in mind that in this case, the space complexity will follow the time complexity exactly as we are literally occupying new space at each iteration. So, in the worst case, the space complexity will be O(n^2).