702 views

What is the space complexity of the following code? 1. $O(logn)$
2. $O(n)$
3. $O(nlogn)$
4. $O(1)$

Can anybody suggest a good resource for understanding how to find space and time complexity of such problems?

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)}$

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.

by