I have the task for my asymptotics class, which is to state whether $f(n) = e^{o(n)}$ the same as $f(n) = o(e^{n})$. I was assuming that it is, because we can present $f(n)$ as $f(n) = e^{g(n)}$, then, $f(n) = o(e^{n})$ means that $\lim \limits_{n\to\infty} \frac{f(n)}{e^{n}} = 0$, which means that $\lim \limits_{n\to\infty} \frac{e^{g(n)}}{e^{n}} = 0$, which means that $\lim \limits_{n\to\infty} {g(n) - n} = -\infty$, and as $g(n)$ is a positive function, that means that it is rising slower than $n$, then, $g(n) = o(n)$, then $f(n) = e^{o(n)}$. But then i googled and found this question, where on of the commenters claimed, that it actually isn't, and now I am stuck trying to explain why.
Asked
Active
Viewed 304 times
3
-
You have to decide if you mean $O(n)$ (in words BIG O) or $o(n)$ (in words small o). These are two different things and the answer will depend on it. – Karl Oct 06 '14 at 13:10
-
@Karl I meant small o, I don't know why it turned out to be big O in the header – Alex Oct 06 '14 at 18:27
2 Answers
4
$f(n)=e^{o(n)}$ means $f(n)=e^{na_n}$, with $a_n\to 0$.
$g(n)={o}(e^n)$ means $g(n)=b_ne^n$, with $b_n\to 0$.
Note that $$ f(n)=e^ne^{n(a_n-1)}=c_ne^n, \quad \text{and $c_n\to 0$}, $$ since $a_n<1/2$, for $n\ge n_0$, some $n_0\in\mathbb N$, as $a_n\to 0$, and hence $n(a_n-1)<-n/2$, and $c_n=e^{n(a_n-1)}\to 0$.
Then $f(n)=o(e^n)$ as well.
On the other hand $$ g(n)=b_ne^n=e^{n+\log b_n}=e^{n(1+\frac{\log b_n}{n})}, $$ and $1+\log b_n/n$ does not necessarily tend to zero, i.e., if $b_n=n^{-1}$, then $$ 1+\frac{\log b_n}{n}=1-\frac{\log n}{n}\to 1. $$ Hence $g(n)$ is not necessarily $e^{o(n)}$.
Yiorgos S. Smyrlis
- 83,933
-
Thanks a lot for answering. I don't understand one thing, though: is $c_n$ represent $e^{n(a_n-1)}$ and if yes, then why does it tends towards zero? – Alex Oct 07 '14 at 09:36
