2

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

  • Indeed, $f(n) = e^{o(1)}$ implies $f(n) \to 1$. So what exactly is your question? – TMM Apr 30 '13 at 15:05
  • 1
    A systematical way to interpret these phenomena is to consider $o$ and $O$ sets of functions. For example, $o(g(n))={f(n):\forall\epsilon>0,\exists N,\forall n\ge N,\lvert f(n)\rvert<\epsilon\lvert g(n)\rvert}$, and $O(g(n))={f(n):\exists M,\forall n,\lvert f(n)\rvert\le M\lvert g(n)\rvert}$, and $f(n)=o(g(n))$ is conventional abbreviation for $f(n)\in o(g(n))$. – Yai0Phah Apr 30 '13 at 15:06
  • 1
    In your example, you can express $f(n) = e^{o(1)}$ as $f(n) = 1 + o(1)$, so you may wonder what's the point of putting an $o(\cdot)$ in the exponent. But if you have $f(n) = e^{o(n)}$, then you cannot rewrite this to something else, and you really need the $o(\cdot)$ in the exponent. (Note that $e^{o(n)}$ is not the same as $o(e^n)$.) – TMM Apr 30 '13 at 15:50

1 Answers1

0

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

Alex
  • 19,262