Textbook
For sufficiently large natural $n$, the functions satisfy $f(n)\ge0$ and $g(n)>0$. The statement $f\in o(g)$ means $\lim_{n\to\infty}f(n)/g(n)=0$. It compares relative size rather than absolute values.
Equivalently, for every $\varepsilon>0$ some threshold $n_0$ ensures $f(n)\le\varepsilon g(n)$ afterward. Unlike big O, the multiplier can be demanded arbitrarily small by moving the start of the tail.
For example, $n\in o(n^2)$ because the ratio is $1/n\to0$. The function $n$ itself does not decrease or tend to zero. But $3n\notin o(n)$: its ratio stays 3, although $3n\in O(n)$ is true.
Negligibility here is asymptotic. At small inputs, constants can make a lower-order contribution numerically significant. Dropping a term in a concrete calculation requires checking its relative contribution at the scale being used.
The threshold $n_0$ may be selected anew for each $\varepsilon$, but the condition must then hold for every larger $n$. Isolated favorable ratios are insufficient. For positive functions, multiplying $f$ by any fixed positive constant preserves membership in $o(g)$: the constant changes the required threshold, while the ratio’s zero limit remains zero.
Definitions and notation: Mathematics for Computer Science.
Related concepts: Limits of sequences, Big O: an upper growth bound.
In plain language
An expense can grow in absolute currency while taking a shrinking share of a budget. Little o requires that share to tend to zero and remain arbitrarily small throughout a sufficiently distant tail. A linear term has this fate beside a quadratic even though the linear term itself keeps growing. “Negligible” concerns relative scales: pocket money can be astronomical for a large enough owner, and one favorable month does not establish a trend.
Example
The constructed example compares $f(n)=n$ and $g(n)=n^2$ through both values and their ratio.
Little o: negligible relative growth
Input 1
The functions are equal here; the ratio is 1.
Step 1 of 4: Input 1
Read all steps
Input 1
The functions are equal here; the ratio is 1.
- f; g; ratio
- 111current
Input 10
The numerator grows, but its share shrinks to 0.1.
- f; g; ratio
- 101000.1current
Input 100
The linear part is now one hundredth of the quadratic.
- f; g; ratio
- 100100000.01included
Any positive share
For any positive tolerance, n above its reciprocal is sufficient.
- Tolerance; sufficient threshold
- 0.001currentn > 1000included
The requirement “below one percent” gives $1/n<0.01$, hence $n>100$. The row at $n=100$ is exactly one percent, so it has not yet met the strict tolerance. Replacing the numerator with $1000n$ requires $n>100000$. It still has lower order, yet can remain significant at moderate inputs. A limit statement therefore does not supply a ready numerical bound for any arbitrary input.
The criterion is the limit of the ratio. Joint growth or an ordinary big-O bound is not enough for little o.