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