# Master theorem: When a $f(n)$ is smaller or larger than $n^{\log_b a}$by less than a polynomial factor

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)$$?

$$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}).$$)

• 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? – Debasis Jana Jun 20 '19 at 11:17
• I think polynomials are variables with integer exponents? – Debasis Jana Jun 20 '19 at 11:20
• How do you find $(logn)^m$? and please tell me how do find other log exponents? – Debasis Jana Jun 20 '19 at 11:33
• Updated. Is it clear now? – John L. Jun 20 '19 at 15:12
• what is mathematical procedure to calculate $(log n)^{1.99}$? – Debasis Jana Jun 21 '19 at 13:58