# small o(1) notation

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

-
You should clarify your question. Even though people may be able to guess what you want to ask, there's no need for anybody to guess. I don't think it will be too hard for you to spend some more time improving your question. – Adrián Barquero Mar 26 '11 at 6:24
I thought the question is clear enough. How exactly do you want me to improve it? – sigma.z.1980 Mar 26 '11 at 14:32

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.

-
Corrected my response. Although I would find out the quantifiers error eventually, thanks for the mod signs, which is something I have never encountered before. – chazisop Mar 26 '11 at 14:07

It probably means $$\lim_{n \to \infty} \frac{f(n)}{1} = 0$$

-
doesn't f(n)=o(g(n)) mean $limf(n)=|\epsilon \cdot g(n)|$? – sigma.z.1980 Mar 26 '11 at 6:24
– PEV Mar 26 '11 at 6:35
whether there is $\epsilon$ or $1$ in the denominator does not matter at all... – Fabian Mar 26 '11 at 6:49
$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$. – GEdgar Jul 3 '11 at 12:40

Suppose that $f(n)\in o(1)$ . This can be interpreted using to equivalent definitions:

1. $\forall$ constant $k>0$ $\exists$ $n_{0}$ such that $\forall n \geq n_{0}$ , $n \epsilon \mathbb{N}$, $|f(n)| \leq k$.

2. $\forall$ constant $k > 0$ , $\lim_{n \rightarrow \infty} \frac{f(n)}{k} = 0$ , which implies that $\lim_{n \rightarrow \infty} f(n) = 0$.

-
$n_{0}$ must be the same for all n and k. So the order is $\exists n_{0} \forall n \geq n_{0} \forall k > 0$. I just mention my background because there may be slight variations on how asymptotic notation are used in analysis that I am not aware of. – chazisop Mar 26 '11 at 8:38
Isn't it possible to come up with some pseudo-random algorithm that has constant running time? For example, if I want a quadruple of numbers between 0 and 1 which make up a nonzero determinant, one randomly generated quadruple will work almost certainly. – Daenerys Naharis Mar 26 '11 at 9:19
@Joseph In certain models it is possible to have constant time algorithms. They would be however $O(1)$ and not $o(1)$. As I mentioned in my answer, an algorithm cannot have a running time less than 1 step,whereas $\forall k$ includes constants less than 1. $o(1)$ of course makes sense for analysis. – chazisop Mar 26 '11 at 9:28
$o(1)$ can come up in expected time analyses of algorithms, e.g. (fictional) $T(n) = 2n + 3 + \frac{1}{n}$. Also, my standard comment: note that $f(n) = o(1)$ is abuse of notation. A function can not equal a class of functions. – Raphael Mar 26 '11 at 10:21
No, $n_0$ is allowed to depend on $k$ in the standard meaning of $o(1)$. $f(n)=1/n=o(1)$, but there is no value of $n_0$ which works for all $k$. For any particular $k$ you can choose $n_0(k)$. See 5316's answer. – Douglas Zare Mar 26 '11 at 13:23