1

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.

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

1 Answers1

1

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.

JavaMan
  • 13,153