Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
I am trying to solve the following recurrence:
$$T(n) = T(n/2) + \left(\log_2(n)\right)^2$$
with $T(1)=1$
I want to find the $\Theta$ bound for the expression.
I came up with an expression to turn this into a summation but it was pointed out by El Pasta to be incorrect.
If $n = 2^m$, then this standard substitution gives $T(n) = T(n/2) + \left(\log_2(n)\right)^2 $ which becomes $T(2^m) = T(2^{m-1}) + \left(\log_2(2^m)\right)^2 = T(2^{m-1}) + m^2 $.
Letting $s(m) = T(2^m)$, this is $s(m) = s(m-1)+m^2 $ with $s(0) = T(1) = 1$ or $s(m)-s(m-1) = m^2$.
Summing $\displaystyle s(n)-s(0) =\sum_{m=1}^n(s(m)-s(m-1)) = \sum_{m=1}^nm^2 =\dfrac{n(n+1)(2n+1)}{6} $ so $\displaystyle T(2^n) =s(n) =s(0)+\dfrac{n(n+1)(2n+1)}{6} =1+\dfrac{2n^3+3n^2+n}{6} $.
Setting $m = 2^n$, so $n = \log_2(m)$, this becomes $\displaystyle T(m) =1+\dfrac{2\log_2^3(m)+3\log_2^2(m)+\log_2(m)}{6} =\dfrac1{3}\log_2^3(m)+O\left(\log_2^2(m)\right) $.
In general, if $\displaystyle T(n) = T(n/2) + \left(\log_2(n)\right)^k $, this will yield $\displaystyle T(m) =\dfrac1{k+1}\log_2^{k+1}(m)+O(\log_2^{k}(m)) $.
