in Algorithms retagged by
681 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)$
in Algorithms retagged by
681 views

4 Comments

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

@Nilzucse

Already answered, check the answers

0
0

2 Answers

3 votes
3 votes
Best answer
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.

 

 

by