Why does QuickSort use O(log(n)) extra space?

Correct, the extra space are the log(n) stack frames. From the Wikipedia article of Quicksort:

There is a more complex version which […] can achieve the complete sort using O(log n) space (not
counting the input) on average (for the call stack).

While you could implement quicksort iteratively (i.e., using a loop instead of recursion), you would then need to maintain an auxiliary stack, because Quicksort has two recursive calls and not just one.

Finally, as other answers have pointed out, O(log(n)) is for pretty much all practical applications very, very small. Every constant factor, like the overhead of your data structure, will have a greater impact on memory usage.

Leave a Comment