0
$\begingroup$

I have this recurrence relation:

$$T(n) = T\left(\left\lceil \frac{n}{2} \right\rceil\right) + T\left(\left\lfloor \frac{n}{2} \right\rfloor\right) + 1$$

and I should solve it with $n = 2^m$

$$\begin{align} T(2^m) &= T\left(\left\lceil \frac{2^m}{2} \right\rceil\right) + T\left(\left\lfloor \frac{2^m}{2} \right\rfloor\right) + 1 \\[6pt] &= T\left(\left\lceil 2^{m-1} \right\rceil\right) + T\left(\left\lfloor 2^{m-1} \right\rfloor\right) + 1 \\[4pt] &=2\cdot T(2^{m-1}) + 1 \end{align}$$

but now I am stuck. How can I get rid of $T(2^{m-1})$?

$\endgroup$
2
  • $\begingroup$ Repeat the process until you get to T(0) and T(1). $\endgroup$ Jan 11 '20 at 13:25
  • $\begingroup$ u mean i should solve $T(2^{m-1})$, but if do that i will get $T(2^{m-2})$ and so on $\endgroup$ Jan 11 '20 at 13:31
1
$\begingroup$

Let $$T(2^m)+1=a_m$$ Then $$a_m = 2a_{m-1}$$ Hence, it forms a geometric progression. So the general term is $$a_m=2^ma_0$$ $$\implies T(2^m)=2^mT(1)+2^m-1$$ Hope you can proceed now.

$\endgroup$
0
$\begingroup$

Once you have got $$T(2^m)=2.T(2^{m-1})+1$$ Let $T(2^m)=2^m.a_m$ put in above we get $$2^m.a_m=2^m.a_{m-1}+1$$ $$\therefore a_m-a_{m-1}=2^{-m}$$ $$. $$ Put values of m = m, m-1 , m-2 ,...,1 and add all we get $$a_m-a_0=\sum_{m=1}^{m} 2^{-m}$$ Where a_0=T(1)=k (say) $$ a_m=k+(1-2^{-m})$$ $$2^mT(2^m)=k+1-2^{-m}$$ $$T(2^m)=(T(1)+1).2^{-m}-1$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.