# 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.

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\,$$!
• 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
• 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