Solve the recurrence of t(n) = t(n/2) + log_2n such that t(1) = 0 and verify using mathematical induction

Question

$t(n) = t(n/2) + log_2n$ , such that $t(1) = 0$

and we're assuming in the solution that n is a power of 2 that is $n = 2^m = log_2n$.

Please help me solve this recurrence, I want to verify if my solution $O(log^2n)$ is correct.

Also, how would I verify my answer using mathematical induction on variable m?

Answer 1

If $n = 2^m$, $t(2^m) =t(2^{m-1})+m $.

Let $s(m) = t(2^m) $.

Then $s(m) = s(m-1)+m $. From this, $s(m) = \frac12 m(m+1) $, so $t(n) =t(2^m) = m(m+1) =\log_2(n)(\log_2(n)+1) =\Theta(\log_2^2(n)) $.