# $t(\lfloor\frac{n}{2}\rfloor)+t(\lceil\frac{n}{2}\rceil)+n=n(\lfloor\log n\rfloor+3)-2^{\lfloor\log n\rfloor +1}$

Given the following recurrence relation:

$$t(1) = 1$$

$$t(n) = t(\lfloor \frac{n}{2} \rfloor) + t(\lceil \frac{n}{2} \rceil) + n$$

How would a proof for the solution $$t(n) = n (\lfloor \log n \rfloor + 3) - 2^{\lfloor \log n \rfloor + 1}$$ look?

I suppose this should be proven by induction.

The base case would be $$t(1) = 1 = 3 - 2 = 1 \cdot (\log 1 + 3) - 2^{\log 1 + 1}$$

Next consider two cases. The case $$n$$ is even and $$n$$ is odd...

Is that correct? And if yes, how would you choose $$n$$? $$n=2k$$ and $$n=2k+1$$?

## 1 Answer

Hint:

If you take the $$2k$$ and $$2k+1$$ approach, your recurrence becomes $$t(2k)=2t(k)+2k$$ $$t(2k+1)=t(k)+t(k+1)+2k+1$$

while your inductive hypothesis becomes $$t(2k)=2k(\lfloor\log k\rfloor+4)-2^{\lfloor\log k\rfloor +2}$$ $$t(2k+1)=(2k+1)(\lfloor\log k\rfloor+4)-2^{\lfloor\log k\rfloor +2}$$

and the inductive step looks reasonably simple, with some care needed when $$k$$ is one less than a power of two. I might start by checking the cases when $$k=1$$, i.e. $$n=2,3$$

• That's plausible thanks. In the end i want $t(2k) = 2k(\lfloor \log 2k \rfloor + 3)-2^{\lfloor \log 2k \rfloor + 1}$ for an even $n$, don't i? – upe Nov 17 '18 at 13:49
• @Peter: yes, though for positive real $x$ you have $\log_2(2x)=\log_2(x)+1$ and so for positive integer $k$ you have $\lfloor \log_2(2k)\rfloor=\lfloor \log_2(2k+1)\rfloor = \lfloor \log_2(k)\rfloor +1$ – Henry Nov 17 '18 at 20:29