Few Big O example

Question

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

Answer 1

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

Answer 2

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

Answer 3

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!