I am confusing with the following example.

  1. $n^{1.001} + n\log n = \Theta ( n^{1.001} )$, why not $n\log n$?

    $c_1 \le \frac{\log n}{n^{0.001}} \le c_2 $


    $c_1\le \frac{n^{0.001}}{\log n} \le c_2$

    For me both are same. Means both are giving some constant range for $c_1$ and $c_2$.

  2. $10 n^3 + 15 n^4 + 100 n^2 2^n = \mathcal O (100n^2 2^n) $

  3. $\frac{6 n^3}{ \log n + 1} = \mathcal O(n^3)$

  • $\begingroup$ It's a rather simple application of the definitions. Where are you having trouble? Note 1/n is between constants 0 and 1, but n/1 is unbounded. The same idea applies to those equations. $\endgroup$ Jul 26, 2013 at 15:10
  • $\begingroup$ I may help to plot it: logn/n^0.001, n^0.001/logn. $\endgroup$ Jul 26, 2013 at 15:42

3 Answers 3


Note that $n^{1.001}+n\log n$ is $n\times(n^{0.001}+\log n)$.

Forget about the first factor and focus on $n^{0.001}+\log n$.

The key point is that, for $n$ large enough, $n^{0.001}$ is larger than $\log n$ (do you know/see that?). Hence $n^{0.001}+\log n$ is eventually between $n^{0.001}$ and $2 \times n^{0.001}$, i.e., is in $\Theta(n^{0.001})$.

Then $n^{1.001}+n\log n$ is in $\Theta(n\times n^{0.001})$, i.e., in $\Theta(n^{1.001})$.

On the other hand, for any fixed $c>0$, $\log n$ is always eventually dwarfed by $c\times n^{0.001}$. Hence $n^{1.001}$ is not $O(n\log n)$.

  • $\begingroup$ I don't x^0.001 grows faster than log n. I used Lybniz and WolphramAlpha to plot x^0.001, and it has almost no growth rate, staying less than 2 and almost 1 well into 1e31, while logn (base 2) is almost 100. $\endgroup$
    – jfa
    Feb 7, 2014 at 18:23
  • $\begingroup$ @JFA: write $l$ for $\log x$. Then $x^{0.001}$ is $\exp(l/1000)$, which you can surely see catches up with $l$ and eventually dwarfs it (think $l=1,000,000,000$), even if it starts slowly. $\endgroup$
    – phs
    Feb 14, 2014 at 6:39

To add on @phs's great answer:

Note that $$ \lim_{n\to \infty} \frac{n^{0.001}}{\log n} = \infty$$ while $$ \lim_{n\to \infty} \frac{\log n}{n^{0.001}} = 0$$ (use L'Hôpital's rule).

For (2), it's quite straight-forward: the term that is "most meaningful", that is, the term that grows the fastest is $n^22^n$. Again, $$\lim_{n\to \infty} \frac{n^22^n}{n^3} = \lim_{n\to \infty} \frac{n^22^n}{n^4} = \infty$$

Finally for (3), $O(n^3/\log n)$ would be correct as well, but the "O" notation gives only upper bound, which needs not necessarily be tight. Thus, $$ \frac{6n^3}{\log n+1} \in O(n^3/\log n) \in O(n^3) \in O(n^4) \in O(2^n) \in ...$$


Remember this dominance rule.It will always help you when you have to make Asymptotic comparisons quickly. I am arranging them in increasing order.

constants < logn < nlog n<$n^2$<$n^3$......<$2^n$<$3^n$.......

The zest is that you classify them into constants,logarithmic,linear and logarithmic and linear ,polynomial and then exponential and so on...

Answer to your question: Asymptotic comparision between $n^{1.001}$ and nlogn. Now the first one is polynomial and the second one is linear and logarithmic.Now observe the dominance rule and we can state that $n^{1.001}$ is asymptotically bigger than nlogn . Hope this helps!


Your Answer

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

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