What does a running-time guarantee of o(n log n) promise that O(n log n) does not, and what may a caller actually rely on?
answer
- compare strict and non-strict inequality
- one allows the bound to be tight
- quantifier flips from exists-c to for-all-c
- the ratio tends to zero
basics
~20 sLittle-o is strictly stronger: o(n log n) means the running time grows strictly slower than n log n — their ratio tends to zero — while O(n log n) permits growth exactly proportional to n log n. Neither promises anything about constants or small inputs.
solid answer
~50 sBig-O is the `<=` of growth rates: `O(n log n)` allows the time to be a constant multiple of `n log n` forever. Little-o is the strict `<`: `o(n log n)` asserts the ratio `T(n) / (n log n)` tends to zero — for *every* constant `c > 0`, eventually `T(n) <= c * n log n`. So a routine documented as o(n log n) is promising its growth class is genuinely below n log n (it might be Θ(n) or Θ(n log log n), for instance), whereas an O(n log n) routine may sit exactly at that class. What a caller may rely on: asymptotically, the routine becomes arbitrarily cheap *relative to* n log n. What a caller may not rely on: any concrete class, any constant factor, or being faster than an O(n log n) routine at any particular input size — the promise is purely about limiting behavior.
go deeper
Recognize that little-o exists and is the strict version of Big-O — 'grows strictly slower than' rather than 'grows no faster than'. You are unlikely to be pressed further at this level.
Be ready to state both definitions and the quantifier difference — one constant that exists versus every constant eventually satisfied — and to give an example in each: 2n log n is O(n log n) but not o(n log n); n is both.
Demonstrate spec-reading judgment: articulate exactly what a strict asymptotic guarantee licenses a consumer to conclude, what it deliberately leaves open, and when you would push a vendor or author for the concrete class instead.
Own the documentation standard: performance guarantees your teams publish should be actionable — a tight Theta or a concrete O class — and asymptotic subtleties like little-o belong in the analysis, not the contract.
## The definitions, side by side - **Big-O (non-strict):** `f(n) = O(g(n))` iff *there exists* a constant `c > 0` and a threshold `n0` with `f(n) <= c * g(n)` for all `n >= n0`. One constant, chosen once, suffices. - **Little-o (strict):** `f(n) = o(g(n))` iff *for every* constant `c > 0` there is a threshold `n0(c)` with `f(n) <= c * g(n)` for all `n >= n0(c)`. Equivalently, `f(n)/g(n) -> 0` as `n -> infinity`. The quantifier flip — *there exists a c* versus *for all c* — is the entire difference, and it is the difference between `<=` and `<` for growth rates. `2 n log n` is O(n log n) but **not** o(n log n): the ratio is a constant 2, which does not tend to zero. Meanwhile `n`, `n log log n`, and `n sqrt(log n)` are all o(n log n): each eventually dips below *any* constant multiple of `n log n`. Every o(g) function is automatically O(g) (take c = 1), but not conversely — little-o names a strictly smaller set. Its mirror image exists too: little-omega, `ω(g)`, means the ratio tends to infinity — strictly faster growth — mirroring o the way `>` mirrors `<`. ## Reading it as a spec Suppose a library documents a batch deduplication pass over catalog records as running in o(n log n) time, while a rival documents O(n log n). What did the first vendor actually promise beyond the second? **Promised:** the routine's growth class sits strictly below n log n. It cannot be Θ(n log n); asymptotically its cost becomes negligible *compared to* an n log n budget. If your capacity model divides projected cost by n log n, that ratio is guaranteed to shrink toward zero as the catalog grows. **Not promised:** - **Any specific class.** o(n log n) is compatible with Θ(n), Θ(n log log n), Θ(n / log log n)... The spec deliberately does not say which. - **Anything at a finite size.** The threshold `n0(c)` depends on c and is not disclosed. At your actual catalog size, the o(n log n) routine may be slower than the O(n log n) rival — hidden constants and small-n behavior are entirely outside the notation's jurisdiction. - **Any operation count.** "Fewer than n log n operations" does not follow; constants are still hidden. ## Why real documentation almost never says little-o A strict asymptotic promise with no named class is hard to act on: engineers provisioning capacity want either a concrete class ("Θ(n)") or a guarantee class ("O(n log n)"), both of which plug into estimates. Little-o's natural habitat is *analysis*, where it does real work: stating that a term is asymptotically negligible ("the rebalancing cost is o(n) and can be ignored against the Θ(n) scan"), or asserting an algorithm beats a known class without committing to how much. When you do meet it in a spec or paper, the reliable reading is exactly the limit statement — nothing more concrete — and the senior move is to ask the author for the actual class if a decision depends on it.
- Why do real library docs almost never use little-o?Because it promises no concrete class and nothing at finite sizes, so there is nothing to plug into a capacity estimate. Engineers want a tight Θ or a usable O guarantee. Little-o earns its keep in analysis — declaring a term asymptotically negligible, or claiming an algorithm strictly beats a class without committing to its exact growth.
- Is there a strict lower-bound analogue of little-o?Yes — little-omega, written ω(g): the ratio f(n)/g(n) tends to infinity, meaning f grows strictly faster than g. It mirrors little-o exactly as > mirrors <, and it relates to Ω the way o relates to O: the strict version of the non-strict bound.
Big-O is 'less than or equal' for growth rates; little-o is the strict 'less than' — it forbids the bound from ever being tight.
saying these in an interview costs you the question
- Treats o(g) and O(g) as interchangeable notation variants
- Claims o(n log n) guarantees fewer than n log n operations at every size
- Thinks little-o implies some specific faster class like Theta(n)