# Master theorem recurrence relation

Consider I have the following recurrence

$$T(n) = 10T(n/3) + \Theta(n^2\log^5 n)\,.$$

Now, by the master theorem, if we evaluate $$n^{\log_{b}{a}}$$, we get $$n^{\log_{b}{a}} = n^{\log_{3}{10}} = n^{2.095}$$. Now, can anyone please explain me, which of the three cases apply? If you plot these functions you can see that $$n^2\log^5 n$$ clearly dominates. So, the answer should be $$\Theta(n^2\log^5n)$$.

However, if you try plugging in values in this calculator, you see that the answer is $$\Theta(n^{\log_{3}{10}})$$. Does anyone have a formal reason? I am still confused as to which of these conditions apply.

## 1 Answer

Plotting isn't foolproof: for any $$k,\varepsilon>0$$, we have $$\log^kn = o(n^\varepsilon)$$ (here, I've cancelled the common term of $$n^2$$). However, you can need to take $$n$$ really big to see it when $$\varepsilon$$ is small (e.g., $$0.095$$) and $$k$$ isn't so small (e.g., $$5$$). Here's the plot for $$0\leq n\leq 10^{131}$$, again with the $$n^2$$ term cancelled, and it looks quite different from your plot up to $$n=10^5\,$$!

Indeed, this question may even have been designed to catch you out if you try to compare the asymptotic growth by plotting instead of by understanding.

• So, can we say that $n^a$ always dominates $n^b(logn)^k$, for $a > b$ and $k > 0$. – Palash Ahuja Sep 24 '18 at 21:38
• Correct. More information in our reference question. – David Richerby Sep 24 '18 at 21:40
• I am worried about the practical implication of this. Most of the real-life cases are going to be $n < 10^{130}$. Shouldn't there be some measure that accurately measures what part of your algorithm is going to dominate at a certain input size?. Theoretically, I am not denying what has been said above. – Palash Ahuja Sep 24 '18 at 21:44
• Yes, this is a limitation of asymptotic analysis. The fact that we completely discard all multiplicative constants is usually a bigger issue, though. There are cases, such as matrix multiplication, where the asymptotically best algorithms aren't actually used because they only win out when the input is very, very big. – David Richerby Sep 24 '18 at 22:01
• We also have a question related to the practical aspects of asymptotic analysis. – David Richerby Sep 24 '18 at 22:03