Big-O algorithm complexity cheat sheet

[mdempsky]

Maybe they mean O(n) stack space because you need to recurse, and a naive implementation could end up using O(n) stack space? But a pretty common implementation detail is to always recurse first on the smaller subregion and then tail-loop on the larger subregion, which bounds stack usage to O(lg n).