CODEWITHSUNDEEP
algorithmrecursionanalysis
warpstar
warpstar

Reputation: 483

Space Complexity of a Recursive Code

Consider the following Java method:

   public static void f(int n) {
    if (n<=1) { 
       System.out.print(n) ; 
       return; 
   }else {
       f(n/2) ;
       System.out.print(n);
       f(n/2);
    }
 } // end of method

Question 3. Let S(n) denote the space complexity of f(n). Which of the following statements is correct?

Upvotes: 1

Views: 2150

Answers (1)

Petar Ivanov
Petar Ivanov

Reputation: 93060

Whenever the function calls itself recursively all local variables remain on the stack and a new set of them are pushed to the stack for the new call. This means that you care how many calls are there at most, in other words what is the maximum depth of the recursion.

It's clear that it's log n, because the successive argumetns are n, n/2, n/4, ..., 1. There is a constant number of local variables, namely 1 (for which space is needed on the stack) therefore the overall space complexity is O(log n).

Upvotes: 6

Related Questions