Asymptotic behavior of $1/\ln n$ and $e^x-1$

354 Views Asked by At

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.

1

There are 1 best solutions below

0
On BEST ANSWER

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