How would I go about finding the time complexity $ T(n) = 8T(\frac{n}{2}) + \mathrm{n}^{log_2n} $ ?
I've tried applying Master Theorem (Case 3), but am unsure if I did it correctly.
First, I set $ \mathrm{n}^{3+\epsilon} \leqslant \mathrm{n}^{log_2n}$ and just compared the exponents so $ 3 +\epsilon \leqslant log_2n$
If I take $ \epsilon = 0.1$ and take $ n \geqslant 9 $ then $ \mathrm{n}^{log_2n} $ should be bounded below by $ \mathrm{n}^{3.1} $ meaning $ f(n) = \Omega(\mathrm{n}^{3.1}) $
Checking the regularity condition:
$ 8\mathrm{n}^{log_2\frac{n}{2}} \leqslant c\mathrm{n}^{log_2n} $ simplifies to
$ \frac{8}{n} \leqslant c $
This is true for all $ n \geqslant 9 $ and $ c = 0.9$ thus the regularity condition is satisfied.
Therefore $ T(n) = \Theta(\mathrm{n}^{log_2n}) $
Is this correct or have I missed something? I tried solving the recurrence via substitution but it becomes so messy I can't make sense of it.
When $n = 2^k$, then the equation becomes:
$$ T(2^k) = 8T(2^{k-1}) + n^k. $$
You may assume that $k \geq 4$ as this is an asymptotic bound (so constants can get absorbed into the big-oh term). Then, apply the master theorem or solve using recurrence relations.
If $n \neq 2^k$, then $2^k < n^{2k+1}$ for a unique $k$. You can argue similarly in this case.