How to interpret little-o notation in an exponent.

2.1k Views Asked by At

The definition for the little-o notation that I am using is the following: We write $f(n)=o(g(n))$ if $|f(n)|\leq c_ng(n)$, where $(c_n)$ is a sequence such that $c_n\to 0$ as $n\to\infty$.

With this in mind, I'm having trouble interpreting the statement $f(n)=e^{o(1)}$.

A first approach I can think of is to interpret that $|f(n)|$ is upper bounded by $e^{c_n}$ where $c_n\to0$. Since $e^0=1$, this is somehow equivalent to say that $|f(n)|\leq 1+d_n$ where $d_n\to0$, and thus $f(n)=1+o(1)$.

If we assume that $f(n)>0$ for all $n$, another interpretation I can imagine is that $\ln(f(n))=o(1)$, and thus $\ln(f(n))\to0$, which would imply $f(n)\to1$ and again, $f(n)=1+o(1)$.

1

There are 1 best solutions below

0
On BEST ANSWER

$f(n)$ is definitely $O(1)$ or in fact it is just 1 because $o(1)$ means some function $\varphi(n)$ that tends to 0, so clearly

$$ \lim_{n \to \infty}e^{\varphi(n)}=e^0=1 $$