It's probably a vey silly question, but I'm confused. Does o(1) simply mean $\lim_{n \to \infty} \frac{f(n)}{\epsilon}=0$ for some $n>N$?
small o(1) notation
-
2I thought the question is clear enough. How exactly do you want me to improve it? – 2011-03-26
3 Answers
This should be a comment to chazisop's answer; I don't have enough rep to make it.
Chazisop, your quantifiers in 1 are the wrong way round, in fact there are two problems. Firstly, saying $\forall k>0 : f(n) \le k$ is simply equivalent to saying $f(n) \leq 0$. The right definition for o(1) is that $\forall k >0\ \exists N\ \forall n \geq N : |f(n)| \leq k$. Note that the $k$-quantifier appears at the start, this is non-negotiable! Secondly, notice the mod signs around $f(n)$. If you are only thinking of nonnegative functions (e.g. the running time of an algorithm) you can omit them, but not for arbitrary functions.
To the OP, no, that's not what o(1) means. There are two problems with what you've written: firstly, what is $\epsilon$? Secondly, what are the $n$ and $N$ supposed to be (I don't mean the $n$ in your limit)? You need to think about this statement more carefully.
The definition of $f(n)$ being $o(1)$ is that $\lim _{n \to \infty} f(n) = 0$. That means that for all $\epsilon>0$ there exists $N_\epsilon$, depending on $\epsilon$, such that for all $n \geq N_\epsilon$ we have $|f(n)| \leq \epsilon$. I guess this definition is probably where your $n>N$ comes from.
-
0Corrected my response. Although I would find out the quantifiers error eventually, thanks for the mod signs, which is something I have never encountered before. – 2011-03-26
It probably means $\lim_{n \to \infty} \frac{f(n)}{1} = 0$
-
0$f(n) = o(1)$ as $n \to \infty$ means $\lim_{n\to\infty} f(n) = 0$. No need for $\epsilon$ or $N$. But, of course, the *definition* of the limit can involve $\epsilon$ and $N$. – 2011-07-03
Suppose that $f(n)\in o(1)$ . This can be interpreted using to equivalent definitions:
$\forall$ constant $k>0$ $\exists$ $n_{0}$ such that $\forall n \geq n_{0}$ , $n \epsilon \mathbb{N}$, $|f(n)| \leq k$.
$\forall$ constant $k > 0$ , $\lim_{n \rightarrow \infty} \frac{f(n)}{k} = 0$ , which implies that $\lim_{n \rightarrow \infty} f(n) = 0$.
-
0Corrected. I consider "=" abuse of notation too, but I thought that it was common to use it out of the TCS scope. Modified anyway. Although I removed the algorithms part, I believe $o(1)$ is exotic for algorithms. – 2011-03-26