Asymptotic Notations

Asymptotic analysis describes how running time grows as n becomes large, ignoring constant factors and small inputs. It lets us say "merge sort is faster than insertion sort" in a precise, machine-independent way.

#Big-O: upper bound

f(n) = O(g(n)) if there exist positive constants c and n₀ such that 0 ≤ f(n) ≤ c·g(n) for all n ≥ n₀.

f grows no faster than g. Example: 3n² + 10n + 5 = O(n²). Choose c = 4: we need 3n² + 10n + 5 ≤ 4n², i.e. n² − 10n − 5 ≥ 0, which holds for all n ≥ 11. So c = 4, n₀ = 11 works.

#Big-Omega: lower bound

f(n) = Ω(g(n)) if there exist positive constants c and n₀ such that 0 ≤ c·g(n) ≤ f(n) for all n ≥ n₀.

f grows at least as fast as g. Example: 3n² + 10n + 5 = Ω(n²) with c = 3, n₀ = 1.

#Big-Theta: tight bound

f(n) = Θ(g(n)) if there exist positive constants c₁, c₂ and n₀ such that c₁·g(n) ≤ f(n) ≤ c₂·g(n) for all n ≥ n₀.

f grows exactly as fast as g. f = Θ(g) if and only if f = O(g) and f = Ω(g). So 3n² + 10n + 5 = Θ(n²).

#Little-o and little-omega

#Order of growth

From slowest to fastest growing:

1 < log log n < log n < √n < n < n log n < n² < n³ < 2ⁿ < 3ⁿ < n! < nⁿ

A quick way to compare two functions: compute lim f(n)/g(n) as n → ∞. If it is 0, f = o(g); if it is a positive constant, f = Θ(g); if it is ∞, f = ω(g).

#Properties

1. Transitivity: if f = O(g) and g = O(h), then f = O(h) (same for Ω, Θ).
2. Reflexivity: f = O(f), f = Ω(f), f = Θ(f).
3. Symmetry: f = Θ(g) if and only if g = Θ(f).
4. Transpose symmetry: f = O(g) if and only if g = Ω(f).
5. Sum rule: O(f) + O(g) = O(max(f, g)).
6. Product rule: O(f) · O(g) = O(f · g).
7. Constants vanish: O(c·f) = O(f) for any constant c > 0.
8. Logs: log_a n = Θ(log_b n) for any bases a, b > 1, so the base is usually omitted.

#Checking bounds numerically

You can watch a ratio settle to a constant (Θ) or shrink to zero (little-o):

#include <cstdio>
#include <cmath>

int main() {
    printf("%10s %16s %16s %16s\n", "n", "f(n)/n^2", "n log n / n^2", "n^2 / 2^n");
    for (double n = 10; n <= 1e6; n *= 10) {
        double f = 3 * n * n + 10 * n + 5;
        printf("%10.0f %16.6f %16.6f %16.3g\n", n, f / (n * n), n * log2(n) / (n * n), n * n / pow(2, n));
    }
    return 0;
}

         n         f(n)/n^2    n log n / n^2        n^2 / 2^n
        10         4.050000         0.332193           0.0977
       100         3.100500         0.066439         7.89e-27
      1000         3.010005         0.009966        9.33e-296
     10000         3.001000         0.001329                0
    100000         3.000100         0.000166                0
   1000000         3.000010         0.000020                0

The first column approaches 3 (so f = Θ(n²)); the second tends to 0 (n log n = o(n²)); the third collapses to 0 incredibly fast (n² = o(2ⁿ)).