How to solve master theorem $T(n) = 3T\left(\frac{n}{2}\right) + \frac{n^2}{\log_2 n}$

Question

Im trying to solve this using master theorem $T(n) = 3T\left(\frac{n}{2}\right) + \frac{n^2}{\log_2 n}$ but I dont know how.

So far we know that $a=3$, $b=2$, $f(n) = \frac{n^2}{\log_2 n}$.

Which rule to apply now and how to solve this?

Answer 1

There are 3 cases to the Master theorem for solving the recurrence $T(n)=aT(n/b)+f(n)=3T(n/2)+n^2 / (\log n)$. If you draw out the recursion tree, the cost of the root is $f(n)$ and the cost of all the leaves is $n^{\log_b a}$. We compare these two costs and we get the three different cases for the Master theorem. Since the cost of the root $f(n) = n^2 / \log n$ is polynomially larger than the cost of the leaves $n^{\log_b a }= n^{\log_2 3} \approx n^{1.6}$, we are in the third case of the Master theorem. This third case asks to also check if a certain regularity condition is satisfied, i.e. whether $af(n/b) \le cf(n)$ for some constant $c$ and all sufficiently larger $n$. This can be verified to be true since $3 (n/2)^2 / (\log n/2) \le c n^2 / (\log n)$ for some constant $c$ and sufficiently large $n$. So, the third case of the Master theorem applies, and we get $T(n) = \Theta(f(n))$, which is $\Theta(n^2 / \log n)$.