retagged by
1,013 views
5 votes
5 votes

What is the space complexity of the following code?

  1. $O(logn)$ 
  2. $O(n)$
  3. $O(nlogn)$ 
  4. $O(1)$
retagged by

2 Answers

Best answer
3 votes
3 votes
First the for loop will run for i =1 to i =n

Then the m value will be $2^n$ now the g($2^n$)is called each time it is decrementing by 2 ,space complexity depends on max size  of stack g(m) function recursively called

Recurrence for it will be take

S(m)=S($\frac{m}{2}$)+1 $\equiv $

$ O(logm)$ $\equiv $ $O(log_22^n)$ $\equiv $ O(n)

so height upto which tree grows is O(n)

Now again f(n/2) will be called untill the function return

S(n)=S($\frac{n}{2}$)+1

$\equiv $ $ O(logn)$

Space complexity is max size of stack

$\equiv $ O(n+logn) $\equiv $ $\mathbf{O(n)}$
selected by
2 votes
2 votes

when the for loop executes and ends for 1st case m = 2n

now this value of m goes to the function g() which runs till ( 2n/2 <=1)

--- means stack space : O(n)

now we goto function f() again which executes for (n/2k<=1) and as n decrements by 1/2 every time.

---its stack space : O(logn)

now as value of function f(n)--->f(n/2) than function g() will have stack space as O(n-1) but for finding stack space we consider only the maximum stack space... 

now cosidering other statements time complexity to be constant. O(1)

overall space complexity : O(n) +O(logn)+O(1) = O(n) solution.

 

 

Related questions

0 votes
0 votes
3 answers
1
iita asked Dec 31, 2016
315 views
4 votes
4 votes
1 answer
2
0 votes
0 votes
1 answer
3
parulnabi asked Sep 2, 2016
582 views
Which of the following algorithm has the smallest memory requirement, including data space and run time stack for recursive calls?A. Insertion SortB. Quick SortC. Selecti...