little-omega notation
/ little oh-MAY-guh /
Little-omega is the mirror image of little-o, the way Big-Omega mirrors Big-O. If little-o means 'eventually negligible', little-omega means 'eventually dominant': f(n) = omega(g(n)) says f outgrows g without limit, so f becomes arbitrarily many times bigger than g as n increases.
Formally, f(n) is omega(g(n)) if for EVERY positive constant c there is a threshold n0 such that f(n) > c times g(n) for all n >= n0 — the same 'for every c' quantifier as little-o, but with the inequality reversed. When the limit exists, the clean test is that f(n) is omega(g(n)) exactly when the limit of f(n)/g(n) as n goes to infinity is infinity (the ratio blows up). For example n^2 is omega(n) because n^2/n = n goes to infinity; and n is omega(log n) because n/(log n) goes to infinity. Notice the perfect duality: f is omega(g) if and only if g is o(f).
You reach for little-omega when you want to say one growth strictly dominates another, more forcefully than Omega allows. Omega(g) permits f to grow at the same rate as g (within a constant); omega(g) forbids that — f must pull strictly ahead. This is the language of 'strictly faster growth', useful in separating complexity classes and in stating that an algorithm is asymptotically worse than another, not merely no better.
Is n^2 little-omega of n log n? Compute n^2 / (n log n) = n / log n, which goes to infinity as n grows (n outpaces log n). Yes, n^2 = omega(n log n): an n^2 algorithm is strictly asymptotically worse than an n log n one. By duality this is the same as saying n log n = o(n^2).
Little-omega is the ratio-goes-to-infinity test, the strict dual of little-o.
omega(g) is strictly stronger than Omega(g): it forbids equal growth. The four notations pair up as O/o (upper) and Omega/omega (lower), with the little versions being the strict ones.