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

Question

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

Answer 1

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.

Answer 2

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