Little o and Little omega

Big O gives an upper bound but does not say whether the bound is tight. The function $n$ is both $O(n)$ and $O(n^2)$; the second statement is true but uninformative.

In some cases, what needs to be said is stronger: “$f$ grows strictly slower than $g$.” This lesson defines the two notations that make that statement possible.

Little o

$$f(n) = o(g(n)) \iff \forall c > 0,\ \exists n_0 : \forall n \geq n_0,\ f(n) < c \cdot g(n)$$

Its difference from big O is in the quantifier. Big O says “a $c$ exists”; little o says “for every $c$” — no matter how small the constant is chosen, the inequality holds for sufficiently large $n$.

The result is that $f$ becomes increasingly negligible next to $g$. An equivalent and useful form is given with a limit:

$$f(n) = o(g(n)) \iff \lim_{n \to \infty} \frac{f(n)}{g(n)} = 0$$

For example, $n = o(n^2)$, because the ratio $1/n \to 0$. By contrast, $3n$ is not $o(n)$: the ratio stays at the constant $3$, it does not go to zero. Big O, however, accepts both — $3n = O(n)$ is true.

Little omega

$$f(n) = \omega(g(n)) \iff \lim_{n \to \infty} \frac{f(n)}{g(n)} = \infty$$

Little omega is little o’s mirror image: $f$ strictly outpaces $g$. $n^2 = \omega(n)$ and $2^n = \omega(n^{100})$ are true — exponential growth eventually overtakes every polynomial.

The Analogy of the Five Notations

The five notations map one to one onto numeric comparisons:

Notation	Comparison analogy	Limit criterion
$f = O(g)$	$f \leq g$	Ratio finite (can be zero)
$f = \Omega(g)$	$f \geq g$	Ratio greater than zero (can be infinite)
$f = \Theta(g)$	$f = g$	Ratio tends to a finite constant greater than zero
$f = o(g)$	$f < g$	Ratio tends to zero
$f = \omega(g)$	$f > g$	Ratio tends to infinity

The analogy is instructive but not exact; the differences are taken up in the final section of this lesson.

Applying the Limit Criterion

The limit is the most practical way to determine the relationship between two functions. The ratio is computed and its behavior as it tends to infinity is examined.

import math

def ratio(f, g, n_values):
    return [f(n) / g(n) for n in n_values]

n_values = [10, 100, 1_000, 10_000, 100_000]

print([f"{x:.4f}" for x in ratio(lambda n: n, lambda n: n**2, n_values)])
# ['0.1000', '0.0100', '0.0010', '0.0001', '0.0000']   — tends to zero: n = o(n²)

print([f"{x:.4f}" for x in ratio(lambda n: 3*n, lambda n: n, n_values)])
# ['3.0000', '3.0000', '3.0000', '3.0000', '3.0000']   — constant: 3n = Θ(n), not o(n)

print([f"{x:.4f}" for x in ratio(math.log2, lambda n: n, n_values)])
# ['0.3322', '0.0664', '0.0100', '0.0013', '0.0002']   — tends to zero: log n = o(n)

print([f"{x:.2f}" for x in ratio(lambda n: n * math.log2(n), lambda n: n**2, n_values)])
# ['0.33', '0.07', '0.01', '0.00', '0.00']             — n log n = o(n²)

A numerical observation is not a proof; that the limit actually goes to zero is shown mathematically. But it is a fast way to confirm an expectation and catch errors.

The third line confirms a frequently used result: a logarithm grows slower than every positive power. The fourth line shows why the difference between $n \log n$ and $n^2$ is so decisive — the ratio tends to zero, meaning the gap widens as the input grows.

Growth Hierarchy

Little o arranges frequently used functions into a strict chain. At every step, the one on the left is little o of the one on the right:

$$1 = o(\log \log n) = o(\log n) = o(n^{\varepsilon}) = o(n) = o(n \log n) = o(n^2) = o(2^n) = o(n!)$$

Here $\varepsilon$ is any constant greater than zero. The chain summarizes three general rules:

• Logarithm grows slower than every positive power. Even $\log n = o(n^{0.001})$ holds; it does not matter how many times the logarithm is applied.
• Every polynomial grows slower than every exponential. $n^{1000} = o(1.001^n)$ holds, no matter how close the base is to one.
• Exponential grows slower than factorial. The average of $n!$’s factors grows along with $n$, while $2^n$’s factors stay constant.

Because every relation in the chain is written with little o, the distinctions between them are strict; moving from one class to another is not a constant-factor improvement but a change of order.

The same chain also gives the link between $\Theta$ and the little notations: if $f = \Theta(g)$, then $f$ is neither $o(g)$ nor $\omega(g)$. The three cases are mutually exclusive and — if the limit of the ratio exists — together cover every possibility.

What It Is For

Little notations are used in three places.

Establishing the class hierarchy. The statements “$\log n = o(n)$ and $n = o(n^2)$” say that complexity classes are strictly separated. The same claim cannot be made with big O; because $O$ may be loose, it does not demonstrate the distinction.

Stating negligibility. If an expression’s smaller term is written with $o(\cdot)$, this states “this term is asymptotically insignificant”: the expression $n^2 + o(n^2)$ states that the second term vanishes next to the dominant term.

A claim of strict separation. That two algorithms are in different classes can only be stated with little notation. “The first is $O(n^2)$, the second is $O(n \log n)$” does not by itself prove the second is better — the first’s bound might be loose. The precise statement is that the second algorithm’s cost is $o(\cdot)$ of the first’s.

Not a Total Order

The comparison analogy breaks down at one point: for numbers, one of two values is always either smaller than, larger than, or equal to the other. For functions, there is no such guarantee.

Two functions can be incomparable: if the ratio between them oscillates, neither a limit exists nor can a bound relation be established. For example, there is no asymptotic relation at all between $n$ and a function that takes the value $n^2$ at odd $n$ and $1$ at even $n$.

def oscillating(n: int) -> int:
    return n**2 if n % 2 == 1 else 1

print([oscillating(n) / n for n in range(1, 8)])
# [1.0, 0.5, 3.0, 0.25, 5.0, 0.16666666666666666, 7.0]   — ratio oscillates

The ratio converges to neither zero nor infinity; it goes back and forth between them. Such a function is neither $O(n)$ nor $\Omega(n)$.

Algorithm costs encountered in practice are regular functions, and this problem does not arise; but knowing that the notation is a partial order requires constructing statements carefully.

Summary

• Little o states that a bound is strictly loose: the inequality holds for every constant, and the ratio tends to zero.
• Little omega is the same relation in reverse; the ratio tends to infinity.
• The five notations resemble numeric comparisons: $O \approx \leq$, $\Omega \approx \geq$, $\Theta \approx =$, $o \approx <$, $\omega \approx >$.
• The limit criterion is the practical way to determine the relationship between two functions.
• Little notations are used to establish the class hierarchy, state negligibility, and make a claim of strict separation.
• The relation is not a total order; functions whose ratio oscillates are incomparable.

Next Step

The notations have been defined; next comes the growth classes they represent. The next lesson will compare, numerically, the classes stretching from constant time to factorial, and answer the question “how large an input can an algorithm handle.”