# Few Big O example

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$

OR

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

• 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. – Bernhard Barker Jul 26 '13 at 15:10
• I may help to plot it: logn/n^0.001, n^0.001/logn. – Bernhard Barker Jul 26 '13 at 15:42

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

• 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. – JFA Feb 7 '14 at 18:23
• @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. – phs Feb 14 '14 at 6:39

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!