2
$\begingroup$

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.

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

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

$\endgroup$
3
  • $\begingroup$ 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? $\endgroup$ – Tez_Nikka Jan 17 '19 at 5:37
  • $\begingroup$ This gives $T(m) = \Theta(\log_2^{k+1}(m))$. $\endgroup$ – marty cohen Jan 17 '19 at 5:46
  • $\begingroup$ I'm sorry I meant to ask what would $T(n)$ be in terms of the $\Theta$ bound? $\endgroup$ – Tez_Nikka Jan 17 '19 at 5:48

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.