= Little o notation
{title2=$f=o(g)$}
When $g$ is nonzero sufficiently near the specified <limit>, little o notation means
$$
\boxed{f=o(g)\quad\Longleftrightarrow\quad f/g\longrightarrow0.}
$$
Thus the numerator becomes negligible relative to the denominator's scale. As $n\to\infty$, $n=o(n^2)$ because $n/n^2=1/n\to0$; as $h\to0$, $h^2=o(h)$ because $h^2/h=h\to0$. The direction of the <limit> changes the comparison. https://ocw.mit.edu/courses/6-042j-mathematics-for-computer-science-fall-2010/93cad640cf3ed0b23ef70688f452d4d5_MIT6_042JF10_notes.pdf#page=281[MIT Mathematics for Computer Science, §9.7.1: little-oh comparison]{ref}
Equivalently, for every $\varepsilon>0$, the bound $|f|\le\varepsilon|g|$ holds sufficiently near that <limit>, with a threshold allowed to depend on $\varepsilon$. <Big O notation> needs only one fixed multiplier, making it weaker. For example, $2n=O(n)$ but $2n$ is not $o(n)$. The useful relation $f\sim g\Longleftrightarrow f-g=o(g)$ turns <asymptotic equivalence> into a statement about a negligible remainder.
Back to article page
