2

Assume $t(1) = 0$. Assume $n$ is a power of $2$, so $n = 2^m$ or $m = \log_2 n$.

I am first asked to solve the recurrence, then asked to prove my answer by induction.

I solved the recurrence and got $O((\log_2(n)^2)$, but dont understand the second part.

Any help is appreciated.

Jean Marie
  • 81,803
throwawayguy
  • 21
  • Do you simply not understand how induction works, or how to prove this particular question using induction? – Skeleton Bow Oct 19 '16 at 21:41
  • You need the exact recurrence solution. After you have that, you take the base as t(1) and show that your solution return 0. You suppose for t(n') = YOUR SOLUTION for all n' < n. And prove that if you suppose this, the t(n+1) using the given recurrence and hyphotesis is the same your solution returns. I found a strange summation, like sum from log(n/2^i) [i = 0 to i = log(n/2)], it`s painful to calculate. The idea is this. – WithoutNameZin Oct 20 '16 at 01:23

0 Answers0