5
$\begingroup$

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?

$\endgroup$
5
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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