Khan Academy: Asymptotic Notation

Asymptotic notation represents the rate-of-growth of the running time of an algorithm as the algorithm's input size n becomes large.

To find asymptotic notation, we express the number of steps in an algorithm as an algebraic function. Then we drop the constant factors and low-order terms. This leaves us with a simplified function such as f(n log n).

We commonly express the rate of growth of an algorithm's running time in big notation.

  • Big-Theta (tight bound) θ gives a growth rate that is very close to the actual growth rate of an algorithm.
  • Big-O (upper bound) gives a growth rate that an algorithm will never exceed. An algorithm can have many O functions of varying precision. That is, if an algorithm's growth rate will never exceed f(1), then it will also never exceed f(n), and will certainly never exceed f(2^n).
  • Big-Omega (lower bound) gives a growth rate that an algorithm will always exceed. There can be many Ω functions (of varying precision) for an algorithm, because if an algorithm's growth rate will always exceed f(2^n), then it will also always exceed f(n), and will certainly always exceed f(1).

We can use Big-Theta, Big-O, and Big-Omega to express an algorithm's worst case, best case, and average running time.

If this does not make sense, check out the Khan Academy's notes on Asymptotic Notation. And, if something doesn't seem quite right, critique me on Twitter @dicshaunary.