little-o notation
/ little OH /
Little-o is Big-O with the brakes off: it says one function is not just bounded by another, but is eventually negligible compared to it. Where O(g) allows f to grow as fast as g (within a constant), o(g) insists that f grows strictly slower, so the ratio f/g shrinks toward zero. Think of f(n) = o(g(n)) as 'f becomes a vanishing fraction of g as n grows'.
Formally, f(n) is o(g(n)) if for EVERY positive constant c there is a threshold n0 (depending on c) such that f(n) < c times g(n) for all n >= n0. The key difference from Big-O is the quantifier: Big-O needs only ONE constant c that works; little-o demands the bound hold for every c, no matter how tiny. The cleanest test, when the limit exists, is that f(n) is o(g(n)) exactly when the limit of f(n)/g(n) as n goes to infinity equals 0. For instance n is o(n^2) because n/n^2 = 1/n goes to 0; and log n is o(n) because (log n)/n goes to 0.
Little-o shows up whenever we want to say 'this term is asymptotically dominated and can be ignored' — it is the formal meaning of 'lower-order term'. Writing a cost as n^2 + o(n^2) means 'n^2 plus stuff that becomes negligible next to n^2'. Note the asymmetry with Big-O: n is O(n) but n is NOT o(n), because n/n = 1 does not go to 0. Little-o is a strictly stronger, strictly smaller-than claim.
Is 100n little-o of n^2? Compute the ratio 100n / n^2 = 100/n, which goes to 0 as n grows. Yes, 100n = o(n^2) — the huge constant 100 does not matter, because little-o tolerates any constant and still wins. But 100n is NOT o(n): the ratio 100n/n = 100 stays fixed at 100, never reaching 0.
Little-o is the limit-of-ratio-equals-zero test; constants cannot save you against a faster-growing g.
o(g) is strictly stronger than O(g): f = o(g) implies f = O(g) but not vice versa. The defining quantifier is 'for every c', not 'for some c'.