I was trying to solve the following question while reviewing master theorem.

Which of the following asymptotically grows faster.

(a) $ T(n) = 4T(n/2) + 10n $

(b) $ T(n) = 8T(n/3) + 24n^2 $

(c) $ T(n) = 16T(n/4) + 10n^2 $

(d) $ T(n) = 25T(n/5) + 20(n\log n)^{1.99} $

(e) They are all asymptotically the same

My calculation says, (a) is $\theta(n^2)$ (b) is $\theta(n^2)$ (c) is $\theta(n^2\log n)$. Now how can I evaluate (d)?

If $f(n)$ is smaller or larger than $n^{\log_b a}$by less than a polynomial factor, how can I solve $T(n)$?


1 Answer 1


$ T(n) = 25T(n/5) + 20(n\log n)^{1.99} $

Note that $(\log n)^m=O(n^\epsilon)$ for all $m,\epsilon\in \Bbb R^+$. In plain words, all polynomials of $\log n$ grows slower asymptotically than all polynomials of $n$. Here we abuse "polynomials" to include functions like $x\to x^k$ for all $k\in\Bbb R^+$ such as $x\to x^{0.618}$ or $x\to x^{2019.46}$. This abuse of the term "polynomial" is common when we are talking about the asymptotic behavior of functions.

In particular, $(\log n)^{1.99}=O(n^{0.005})$.

Since $(n\log n)^{1.99}=n^{1.99}(\log n)^{1.99}= O(n^{1.995})=O(n^{log_525-0.005})$, you can apply the case 1 of Master theorem. $T(n)=\Theta(n^2)$.

If $f(n)$ is indeed smaller or larger than $n^{\log_b a}$by less than a polynomial factor, then we are running into the cases strictly between case 1 and case 2 or between case 2 and case 3. The master theorem you were reviewing cannot be applied any more.

You may look into this answer that handles some of those situations.

Exercise. Show that $(\log n)^m=O(n^\epsilon)$ for all $m,\epsilon\in \Bbb R^+$. (For example, $(\log n)^{10000000}=O(n^{0.000001}).$)

  • $\begingroup$ I would like to ask one more thing, in your comment and in the link I provided, there ϵ symbol is used and this ϵ is a real number or natural number? $\endgroup$ Jun 20, 2019 at 11:17
  • $\begingroup$ I think polynomials are variables with integer exponents? $\endgroup$ Jun 20, 2019 at 11:20
  • $\begingroup$ How do you find $(logn)^m$? and please tell me how do find other log exponents? $\endgroup$ Jun 20, 2019 at 11:33
  • $\begingroup$ Updated. Is it clear now? $\endgroup$
    – John L.
    Jun 20, 2019 at 15:12
  • $\begingroup$ what is mathematical procedure to calculate $(log n)^{1.99}$? $\endgroup$ Jun 21, 2019 at 13:58

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.