I want to solve the following using master theorem.

$T(n)=4T(n/8) + \sqrt n (\log_2 n)^2$

I have: $a=4, b=8,f(n)=\sqrt n (\log_2 n)^2$

I calculate $n^{log_b a} = n^{\log_8 4} = n^{2/3}$

I compare $f(n)=\sqrt n (\log_2 n)^2$ with $n^{2/3}$, and see that $f(n)$ grows faster than $n^{2/3}$.

So using master theorem, rule 3, $f(n) \in \Omega (n^{2/3 +some \ c})$, which means $T(n) \in \Theta(f(n))$

But I guess this isn't correct, according to this master theorem calculator tool I used to check my answer.

Where's the mistake?

  • 3
    $\begingroup$ It might help if you would describe your reasoning that $f(n)$ grows faster than $n^{2/3}$. It doesn't. $\endgroup$ – Rick Decker Mar 3 '20 at 1:43
  • $\begingroup$ @RickDecker thanks this was a stupid mistake indeed! $\endgroup$ – Mandy Mar 3 '20 at 2:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.