# 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. Mar 26, 2011 at 6:24
• I thought the question is clear enough. How exactly do you want me to improve it? Mar 26, 2011 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) \leqslant k$$ is simply equivalent to saying $$f(n) \leqslant 0$$. The right definition for $$o(1)$$ is that $$\forall k > 0\ \exists N\ \forall n \geqslant N :\; |f(n)| \leqslant k.$$
Note: the $$k$$-quantifier appears at the start, this is non-negotiable! Secondly, notice the absolute value 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 \geqslant N_\epsilon$$ we have $$|f(n)| \leqslant \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. Mar 26, 2011 at 14:07
• @chazisop By "mod sign" Matthew means the absolute value signs, and (I mean this neutrally) it's surprising you haven't seen them before, so I suspect you might have misconstrued his intended meaning. Absolute value is sometimes called "modulus" especially when referring to the absolute value of complex numbers, but I find this disfavorable because absolute value means only one thing, while modulus is more commonly used to indicate the base of a modular congruence relation. I actually hadn't encountered "modulus" being used to mean absolute value prior to seeing this response. Apr 17, 2021 at 1:29
• @TrixieWolf you're right that absolute value is more common - I updated the answer. Feb 8, 2023 at 15:25

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)|$? Mar 26, 2011 at 6:24
• Mar 26, 2011 at 6:35
• whether there is $\epsilon$ or $1$ in the denominator does not matter at all... Mar 26, 2011 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$. Jul 3, 2011 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. Mar 26, 2011 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. Mar 26, 2011 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. Mar 26, 2011 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. Mar 26, 2011 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. Mar 26, 2011 at 13:23