As Wikipedia says, quickSort needs O(log n) extra space when the following conditions are met:

  • In-place partitioning is used. This unstable partition requires O(1) space.
  • After partitioning, the partition with the fewest elements is (recursively) sorted first, requiring at most O(log n) space. Then the other partition is sorted using tail recursion or iteration, which doesn't add to the call stack. This idea, as discussed above, was described by R. Sedgewick, and keeps the stack depth bounded by O(log n).

Now please consider the following method computing the factorial of n recursively:

private static int fact(int n) {
    if (n == 1) {
        return n;
    return n * fact(n - 1);

There is no tail recursion. Does it mean that we need O(n) extra space for the call stack?


1 Answer 1


Yes, you need up to $n$ stack frames for the recursion. Therefore, you'll need $\Theta(n)$ space for these stack frames.

  • $\begingroup$ Why Big Theta rather than O? $\endgroup$ Commented Jun 29, 2015 at 7:12
  • 2
    $\begingroup$ @MaksimDmitriev See our reference question. $\endgroup$
    – Raphael
    Commented Jun 29, 2015 at 10:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.