6 ms·
What if you always recurse into the smaller half, and use tail-recursion/looping to process the rest? Doesn't that keep the space usage bounded to O(log(n))?
by eutectic 10y ago
What if you always recurse into the smaller half, and use tail-recursion/looping to process the rest? Doesn't that keep the space usage bounded to O(log(n))?
- deathanatos 10y agoThis is correct, and is noted in the Wikipedia article's discussion of memory usage[1]. (Which I was only reading because I was erroneously thinking that quicksort was O(1) memory – I was completely forgetting stack space.) [1]: https://en.wikipedia.org/wiki/Quicksort#Space_complexity https://en.wikipedia.org/wiki/Quicksort#Space_complexity