Asymptotic growth rate of $T(n) = 8T(\frac{n}{2}) + \mathrm{n}^{\log_2 n}$

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.

• There's probably a typo here - do you mean to have a + in the equation? Mar 1 '19 at 1:41
• Yes thank you for pointing that out Mar 1 '19 at 1:43
• ${\log_2 n}$ is surely going to be larger than 3 eventually, so it cannot be the same order as $n^3$. Mar 1 '19 at 1:45
• Oh! Another mistake, thank you for pointing that out! I misread the case 3 for master theorem. I've edited it to say its the order of $\mathrm{n}^{log_2n}$ Mar 1 '19 at 1:52
• Essentially correct. You have a typo in $8 f(n/2)$, if $f(n) = n^{\log_2 n}$, then $$\frac {8 f {\left( \frac n 2 \right)}} {f(n)} = \frac {16} {n^2},$$ which can be bounded from above by any constant. $f(n)$ itself can be bounded from below by any polynomial. Therefore we indeed have that $T(n)$ grows as $f(n)$. Mar 1 '19 at 4:47

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.