# Find tight bound on $T(n) = T(n/2) + \log^2(n)$

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.

• Your expression is strange, $\sum_{0}^{\log(n)}$ is very weird, because $\log(n)$ in generally is not a integer number – El borito Jan 17 '19 at 4:38
• Sorry, thank you for pointing that out. Then I don't have a clue how to solve this. – Tez_Nikka Jan 17 '19 at 4:39
• Relax, Do you have an initial condition as $T(1)=$ a number? – El borito Jan 17 '19 at 4:46
• Yes $T(1) = 1$. Sorry for missing out on this information. First time asking a question here :) – Tez_Nikka Jan 17 '19 at 4:48
• Try using the master theorem – El borito Jan 17 '19 at 5:01

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))$$.

• I'm sorry I don't understand. How do we go from $T(m)=\frac{1}{k+1}log^{K+1}(m) + O(log^k(m))$ to finding the $\Theta$ bound for the recurrence? – Tez_Nikka Jan 17 '19 at 5:37
• This gives $T(m) = \Theta(\log_2^{k+1}(m))$. – marty cohen Jan 17 '19 at 5:46
• I'm sorry I meant to ask what would $T(n)$ be in terms of the $\Theta$ bound? – Tez_Nikka Jan 17 '19 at 5:48