Someone on a hiring loop asked me, "is n little-o of n^2?" I said yes, the candidate said no, and we spent ten minutes arguing about it after the interview. The candidate was wrong. But the deeper problem was that neither of us had a clean mental model for the difference between Big-O and little-o, and we both confidently produced an answer using mostly vibes. The next week I sat down with a textbook and figured out exactly what each notation claims, and exactly when those claims differ.

I want to walk through the five asymptotic notations (O, Omega, Theta, o, omega), separate the ones I use weekly from the ones I would happily forget, and stake out a position: little-o is mathematically interesting and almost never the right tool when you are arguing about real code.

The five notations, in one paragraph each

O(g(n)) (Big-O) is an upper bound. Saying f(n) = O(g(n)) means f grows no faster than a constant times g, eventually. It is the asymptotic version of "less than or equal to". This is the one you have used a thousand times.

Omega(g(n)) (big-Omega) is a lower bound. Saying f(n) = Omega(g(n)) means f grows at least as fast as a constant times g, eventually. The asymptotic ">=". You see this in lower-bound proofs ("any comparison sort is Omega(n log n)"), almost never in code review.

Theta(g(n)) (big-Theta) is a tight bound. f(n) = Theta(g(n)) means f is both O(g) and Omega(g). The asymptotic "==". Industry uses Big-O when it actually means Theta, and that is fine as long as everyone knows we are doing it.

o(g(n)) (little-o) is a strict upper bound. f(n) = o(g(n)) means f grows strictly slower than g. The asymptotic "<", not "<=". Crucially, n is O(n^2) but also o(n^2). n^2 is O(n^2) but it is NOT o(n^2).

omega(g(n)) (little-omega) is a strict lower bound. f(n) = omega(g(n)) means f grows strictly faster than g. Asymptotic ">", almost never seen in industry contexts.

The "<= vs <" distinction that catches people

This is the bit that the candidate and I argued about. Big-O is "less than or equal". Little-o is "strictly less than". Concretely:

• n^2 is O(n^2) ✓ (n^2 is not greater than a constant times n^2)
• n^2 is o(n^2) ✗ (n^2 is not strictly less than n^2 asymptotically; the ratio does not go to zero)
• n is O(n^2) ✓ (n grows no faster than n^2)
• n is o(n^2) ✓ (n / n^2 = 1/n -> 0)

The formal version is the limit definition. f(n) = o(g(n)) if and only if lim (f(n) / g(n)) = 0 as n -> infinity. f(n) = O(g(n)) if the same ratio is bounded above by a constant. The strictness of little-o is what forces that ratio to actually go to zero, not just stay bounded.

In plain words: O lets you put n^2 inside a class of "things that grow at most as fast as n^2", which includes n^2 itself. o excludes n^2 from the class of "things that grow strictly slower than n^2", because nothing strictly grows slower than itself.

A small numerical sanity check

If the limit definition feels abstract, here is a table of ratios for a few function pairs at growing n. The pairs that are little-o have ratios that go to zero; the pairs that are Big-O but not little-o have ratios that stay bounded.

The "constant times the same growth rate" pair (last row) shows why little-o is strict: even though 100n^2 is O(n^2), the ratio stays at 100 forever; it never goes to zero, so 100n^2 is NOT o(n^2). Constants do not buy you a strict-inequality claim.

Where each notation actually shows up

Let me sort them by how often I genuinely use them.

The asymmetry is real. In industry we have a near-universal convention that "Big-O" means "Theta" (a tight asymptotic bound), so the two practical notations collapse into one. Little-o is a much sharper claim ("strictly slower") that we rarely need to make in code review, because in practice we want to know "what class is this in" rather than "is this strictly inside a smaller class".

A worked example: where little-o would actually matter

To be fair, there is one place little-o is genuinely useful: in algorithm-improvement claims that need to express "asymptotically faster than the obvious solution". Consider matrix multiplication. The naive algorithm is Theta(n^3). Strassen's algorithm is O(n^2.81). The most recent academic result is O(n^2.371). To say "strictly faster than n^3", a researcher writes o(n^3). That is the precise mathematical claim: the running time, divided by n^3, goes to zero in the limit.

If they had written O(n^3), that would be technically true but uninformative; everything that runs in O(n^2.81) is also O(n^3). The little-o is doing real work in distinguishing the new bound from the obvious one. In an academic paper, the precision matters. In a code review where someone says "this is O(n)", I do not care whether they mean Theta(n) or o(n^2). I care whether the algorithm is fast enough on the input we expect.

The trap I see in interviews

When candidates panic-quote the more exotic notations, they usually get them wrong. Two mistakes I see often:

First, claiming "n is little-omega of 1" when they mean "n grows faster than 1". Strictly speaking, this is true (lim (n / 1) -> infinity), but the candidate almost always means Big-Omega, not little-omega, and the strict-vs-non-strict distinction does not affect the question being asked. When asked, "what is the lower bound on this algorithm", the right answer is Omega(...), not omega(...).

Second, claiming "this is O(2^n) but also o(3^n)" as if those two statements add information. They do not really; o(3^n) is a much weaker claim than O(2^n) because every function that is O(2^n) is automatically o(3^n) by virtue of 2^n / 3^n -> 0. Stacking little-o claims on top of Big-O claims adds no new information, but it makes the candidate sound like they are flexing notation they do not understand.

The clean approach in interviews is to use Big-O (or Theta if you want to be precise about tightness) and stop. Lower bounds get Omega. Reach for little-o only when you can articulate what tighter claim it lets you make, and only when the audience cares.

A small mental model

The way I keep these straight in my head:

Big-O      <=    "no faster than"
Big-Omega  >=    "no slower than"
Big-Theta  ==    "exactly this rate"
little-o   <     "strictly slower than"
little-omega >   "strictly faster than"

The two "strict" notations exclude equality. That is the entire structural difference. n^2 = O(n^2) is true; n^2 = o(n^2) is false. Once that one fact is locked in, everything else falls out of the "<= vs <" mapping.

Why I almost never bother with little-o

In ten years of writing code professionally, I have never said "this function is little-o of n^2" in a code review and meant it productively. Every time I have wanted to say that, I have actually meant "this function is O(n log n)", which is a stronger and more useful claim. The little-o version says "strictly faster than n^2", which is a much weaker statement; n^1.99 and n / log log log n are both little-o of n^2, and one of those is essentially as bad as n^2 while the other is essentially linear. Telling me a function is o(n^2) does not actually narrow down its behaviour in any way I find useful.

When an algorithm researcher publishes a new matrix multiplication bound, the little-o phrasing is doing real work. When a colleague tells me their function is fast, I want a concrete bound, not a strict-inequality claim against a worse bound. Big-O (used to mean Theta), supplemented with Big-Omega when discussing lower bounds, is the toolkit I actually need. The other three notations are fine to know for interview-trivia reasons and for reading academic papers, but they are not earning their keep in my day job, and I am comfortable saying that out loud.