General Algorithmic Techniques & Analysis

An asymptotic upper bound on a function's growth: f(n) = O(g(n)) means f(n) ≤ c·g(n) for some constant c and all sufficiently large n. It ignores constant factors and lower-order terms.

Ω(g) is an asymptotic lower bound. Θ(g) is a tight bound: f grows exactly like g, bounded both above and below by constant multiples of g for large n.

As n grows large, the highest-order term dominates and constants reflect machine/implementation details, not the algorithm's intrinsic scaling. Asymptotics capture how cost grows with input size, independent of hardware.

O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ). Constant, then logarithmic, linear, linearithmic, quadratic, then exponential.

Rough guides: O(n) and O(n log n) handle n up to ~10⁸ and ~10⁶–10⁷; O(n²) up to ~10⁴; O(2ⁿ) only up to n ≈ 20–25. Use n to pick the target complexity.

It gives the asymptotic solution of divide-and-conquer recurrences of the form T(n) = a·T(n/b) + f(n), by comparing f(n) against n^(log_b a) to determine which term dominates.