1
$\begingroup$

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.

$\endgroup$

1 Answer 1

2
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ So, can we say that $n^a$ always dominates $n^b(logn)^k$, for $a > b$ and $k > 0$. $\endgroup$ Sep 24, 2018 at 21:38
  • $\begingroup$ Correct. More information in our reference question. $\endgroup$ Sep 24, 2018 at 21:40
  • $\begingroup$ 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. $\endgroup$ Sep 24, 2018 at 21:44
  • 1
    $\begingroup$ 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. $\endgroup$ Sep 24, 2018 at 22:01
  • 1
    $\begingroup$ We also have a question related to the practical aspects of asymptotic analysis. $\endgroup$ Sep 24, 2018 at 22:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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