Dark Mode

102 views

1 vote

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