Test Series

Question

What is the time complexity of the below mentioned recursive function.

int f(n)

{

  if(n!=1)

{

  return f(n/2)+f(n/2);

}

else

return 10;

}

 

 

• A. O(n)
• B. O(n^2)
• C. O(log n)
• D. O(n logn)

Answer 1

T(n) = 2T(n/2)+O(1)

using master theorem:

a=2,b=2 k = 0

a>(b^k)

so, time = O(n)

using case 1(given below):

 

Answer 2

This recursive relation can be written ,

$T(n)=2T(n/2)+1$

$T(n)=2(2T(n/4)+1)+1=4T(n/4)+2+1$

$T(n)==4(2T(n/8)+1)+2+1=8T(n/8)+4+2+1$

---

$T(n)=2^{k}T(n/2^{k})+2^{k-1}+2^{k-2}+.......+4+2+1$

$T(n)= 2^{k}T(\frac{n}{2^{k}})+\frac{2^k-1}{2-1}$

let assume ,

$\frac{n}{2^{k}}=1$

$k=logn$

$T(n)=nT(1)+(n-1)$  

$T(1)=c$    [c is some constant]

$T(n)=c*n +n-1$

so ,

$T(n)=O(n)$

 

---

alternate method masters theorem,

$T(n)=2T(n/2)+1$

so by masters theorem,

$n^{\log_{2}2} >1$

$n >1$

so ,$T(n)=\theta (n)$=>$T(n)=O (n)$

 

so correct answer is option a,b,d.

as if $T(n)=O (n)$ ,so

$T(n)=O (n^{2})$

$T(n)=O (nlogn)$