0
$\begingroup$

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

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

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

$\endgroup$
  • $\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 '14 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 '14 at 6:39
3
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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!

$\endgroup$

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.