Asymptotic notation

f(n) = O(g(n)) means there are constants c > 0 and n₀ such that f(n) ≤ c · g(n) for all n ≥ n₀. It is an upper bound: f grows no faster than g, up to a constant factor. Example: 3n² + 5n + 7 = O(n²) with c = 4 and n₀ = 7 (check: 3n² + 5n + 7 ≤ 4n² when n² ≥ 5n + 7, true for n ≥ 7).

Use the explorer: choose f and g, then move c and n₀ until the green region shows f below c · g from n₀ onward. That pair is a witness.

f(n) = Ω(g(n)) means f(n) ≥ c · g(n) for all n ≥ n₀: a lower bound. Example: 3n² + 5n + 7 = Ω(n²) with c = 3 and n₀ = 1, since the extra terms are positive.

Ω is used for “at least this much work”: any comparison sort is Ω(n log n) in the worst case. Switch the explorer to “Lower bound” to look for a c and n₀ with f above c · g.

f(n) = Θ(g(n)) means f is both O(g) and Ω(g): it is bounded above and below by constant multiples of g for large n. So 3n² + 5n + 7 = Θ(n²), with constants 3 and 4. Θ states exactly how a cost grows.

Saying “binary search is O(n)” is true but weak; “Θ(log n) in the worst case” is precise.

f(n) = o(g(n)) means f grows strictly slower than g: for every c > 0 there is an n₀ with f(n) < c · g(n) for n ≥ n₀, equivalently f(n)/g(n) → 0. So n = o(n²) and log n = o(n), but n² ≠ o(n²).

Little-o is a strict inequality between growth classes, while big-O allows equal growth.

f(n) = ω(g(n)) means f grows strictly faster than g: f(n)/g(n) → ∞. So n² = ω(n) and 2ⁿ = ω(n¹⁰⁰). It is the strict counterpart of Ω.

f = ω(g) holds exactly when g = o(f).

An upper bound on an algorithm says it never costs more than this; a lower bound says it never costs less. A problem has its own bounds too: a problem's upper bound is the cost of the best known algorithm, and its lower bound is what any algorithm must spend. When they meet, the problem is solved optimally; comparison sorting has both at Θ(n log n).

Bounds should say which case they cover: worst, average or best.

A bound is tight when it is Θ: it cannot be improved by more than a constant factor. A loose bound is still correct but unhelpful, such as saying insertion sort is O(n³). Always report the tightest bound you can prove.

Test the tightness of a witness in the explorer: if you can also find a lower witness with the same g, the bound is tight.

In a sum of terms, the fastest-growing term dominates for large n, so lower-order terms are dropped: 5n³ + 100n² + 1,000n + 10⁶ = Θ(n³). The order from slowest to fastest is 1, log n, √n, n, n log n, n², n³, 2ⁿ, n!.

Be careful: the cost of different phases adds, so it is O(max), but costs inside nested loops multiply.

Big-O hides constants, and constants decide real speed for realistic n. An algorithm that costs 1000n beats 2n² only when n > 500. Cache misses, allocation and memory layout contribute large constants, so a “slower” O(n log n) on arrays can beat an O(n) algorithm on a linked structure for medium n.

Use the crossing-point view of the explorer: move c and see where two functions swap order.

1// 1000*n vs 2*n*n: equal when n = 500
2long lin = 1000L * n, quad = 2L * n * n;
3boolean linearWins = lin < quad;     // true for n > 500