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

Dark Mode

681 views

5 votes

0

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

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

2 votes

when the for loop executes and ends for 1st case **m = 2 ^{n}**

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

--- means **stack space : O(n)**

now we goto **function f()** again which executes for **(n/2 ^{k}<=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}**.