I am trying to solve the following recurrence relation using the master theorem:
$T(n) = 4T({n/2}) + \theta(n\log{n})$
So:
$a = 4$, $b = 2$, and $f(n) = n\log{n}$
So we are comparing:
$n^{log_b{a}}$ with $n\log{n}$
$n^{log_2{4}} = n^2$ so we are comparing $n^2$ with $n\log{n}$
Now i know that $n^2$ is larger but is it polynomial larger than $n\log{n}$?
Can I apply the master theorem to this problem, if so which case applies to this problem?
Any help would be appreciated.