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



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$

  • $\begingroup$ 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? $\endgroup$ – upe Nov 17 '18 at 13:49
  • $\begingroup$ @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$ $\endgroup$ – Henry Nov 17 '18 at 20:29

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.