Big-O and little-o both compare how fast functions grow as input size becomes large, but they make different claims. Big-O says a function does not grow faster than a reference function up to a constant factor. Little-o says the function grows strictly more slowly. That difference is small in notation and large in meaning.

Big-O Is a Non-Strict Upper Bound

We write f(n) = O(g(n)) when there are constants c > 0 and n0 such that:

f(n) <= c * g(n) for all n >= n0

In plain language, once n is large enough, f(n) stays below some constant multiple of g(n).

This allows f(n) and g(n) to grow at the same asymptotic rate. For example:

• 3n^2 + 5n + 7 is O(n^2)
• n^2 is also O(n^2)

So Big-O does not require strict separation.

Little-o Is a Strict Upper Bound

We write f(n) = o(g(n)) when for every constant c > 0, there exists n0 such that:

f(n) < c * g(n) for all n >= n0

This is stronger than Big-O. It says f(n) eventually becomes smaller than every positive constant multiple of g(n).

An equivalent limit test is:

lim f(n) / g(n) = 0

If the ratio goes to zero, then f(n) is little-o of g(n).

Concrete Examples

Example 1:

• 3n^2 + 5n + 7 is O(n^2)
• it is not o(n^2)

Why not? Because the ratio:

(3n^2 + 5n + 7) / n^2

approaches 3, not 0.

Example 2:

• n is o(n log n)

because:

n / (n log n) = 1 / log n

and 1 / log n goes to 0.

Why Engineers Usually Say Big-O

Big-O is the standard language for algorithm analysis because it answers the practical question: "How bad can this get, ignoring constant factors?"

That is why you commonly see statements like:

• binary search is O(log n)
• merge sort is O(n log n)
• nested loops over n items often give O(n^2)

Little-o is more common in proofs and theoretical comparisons where strict asymptotic separation matters.

A Small Numerical Check

The following Python code prints the ratio n / (n log2 n) for increasing values of n. The ratio gets smaller and smaller, which is the behavior little-o captures.

1import math
2
3for n in [8, 16, 32, 64, 128, 256]:
4    ratio = n / (n * math.log2(n))
5    print(n, round(ratio, 4))

Expected output:

18 0.3333
216 0.25
332 0.2
464 0.1667
5128 0.1429
6256 0.125

The shrinking ratio supports the claim that n = o(n log n).

Comparison Table

Common Pitfalls

• Saying n^2 = o(n^2). That is false.
• Treating Big-O as an exact runtime instead of an asymptotic bound.
• Proving only O(g(n)) and then claiming o(g(n)).
• Forgetting that little-o is stronger than Big-O, not just a stylistic variation.

Summary

• Big-O is a non-strict upper bound.
• Little-o is a strict upper bound.
• f(n) = O(g(n)) allows the same asymptotic growth rate.
• f(n) = o(g(n)) requires f(n) / g(n) to approach 0.
• Big-O is the everyday tool; little-o is for sharper asymptotic statements.