1
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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