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.

  • $\begingroup$ There's probably a typo here - do you mean to have a + in the equation? $\endgroup$ Mar 1 '19 at 1:41
  • $\begingroup$ Yes thank you for pointing that out $\endgroup$
    – D. Prez
    Mar 1 '19 at 1:43
  • $\begingroup$ ${\log_2 n}$ is surely going to be larger than 3 eventually, so it cannot be the same order as $n^3$. $\endgroup$
    – Yimin
    Mar 1 '19 at 1:45
  • $\begingroup$ 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} $ $\endgroup$
    – D. Prez
    Mar 1 '19 at 1:52
  • $\begingroup$ 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)$. $\endgroup$
    – Maxim
    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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.