Big-O, big-Theta and big-Omega

Overview

Defines the three common bounds and shows how to read them from a piece of code.

Big-O gives an upper bound on growth, big-Omega a lower bound, and big-Theta a tight bound when the two agree. In everyday use, people say 'O(n log n)' to mean the tight bound; be aware of the imprecision.

To estimate the complexity of a loop, count how many times the innermost statement runs as a function of the input size, then keep only the fastest-growing term.