I have two asymptotic notation questions.

Determine whether or not $\frac{1}{\ln(n)}=O(\frac{1}{n})$

My answer I put the statement is not true. A logarithmic function $\frac{1}{\ln(n)}$ grows faster $\frac{1}{n}$ regardless of constant placed on $\frac{1}{n}$.

Thus $\frac{1}{\ln(n)}$ not upper bound by $O(\frac{1}{n})$

My second question is

Show that $e^x-1=O(x^2)$ is not true.

But I think it is true because using a graph you see

using a constant c=3 $e^x-1=O(3x^2)$ for $x>0.413$ but I am not sure if this is correct.

  • $\begingroup$ No, it is not correct. $e^x-1$ grows much faster, because it is "an exponential". . "Using a graph" is not really convincing here. $\endgroup$ – Dietrich Burde Sep 6 '15 at 18:38
  • $\begingroup$ Yes I think because e^x-1 is exponetial. $\endgroup$ – Fernando Martinez Sep 6 '15 at 18:41
  • $\begingroup$ What is the definition of big O that you are using? Normally, this is defined with the limit of a ratio, and this should be a useful way to proceed in both questions. $\endgroup$ – process91 Sep 6 '15 at 19:06
  • $\begingroup$ I have f(x)=0(g(x)) f(x)<=Cg(x) for all x>N $\endgroup$ – Fernando Martinez Sep 6 '15 at 19:41
  • 1
    $\begingroup$ Big O notation is the proper formalization for growing slower/faster than. So you should better use the formal definition, instead of intuitive arguments. In both cases, you could use l'hopital. $\endgroup$ – user251257 Sep 7 '15 at 1:17

From the power series for $e^x$, $e^x > \frac{x^{n+1}}{(n+1)!} $, so $\frac{e^x}{x^n} >\frac{x}{(n+1)!} \to \infty $, so $e^x \ne O(x^n)$ for any $n$.


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.