Algorithms · topic
O, Omega, Theta, little-o and little-omega with their constants, limit test and properties; the growth ladder with logs, powers, exponentials and factorials; comparing functions by logarithms; counting loop iterations exactly; worst, best and average case; space and recursion stack; recurrences by substitution, recursion tree and the master theorem with its cases and its limits.
The exact running time of a program depends on the machine, the compiler and the input. To compare algorithms rather than programs, we describe how the running time grows as the input size n grows, ignoring constant factors and small inputs.
Asymptotic notation says how to compare growth rates. This note shows how to obtain the function to compare: how to count the work done by loops, nested loops and recursive calls, and how much memory a program needs beyond its input.
The running time of a recursive algorithm is naturally described by a recurrence: an equation that gives T(n) in terms of T on smaller inputs. Merge sort splits an array into two halves, sorts each and merges in linear time, so T(n) = 2T(n/2) + Θ(n).
One-page visual sheets for this topic, in the sheet library on the store. Previews are free; the full sheets come with the subject pack.
