# How to use master theorem to solve $T(n)=4T(n/8) + \sqrt n (\log_2 n)^2$

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?

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