China Cat my RAM

The Big O ^{(…not that kind of O)}

I got this list from a Princeton site, but here's my condensed, I-wasn't-smart-or-rich-enough-for-Princeton version.

O(1): constant
Running time is the same no matter how many inputs you have (N).

O(log N): logarithmic
Gets slightly slower as N grows. When N doubles, the running time increases by a constant.
Example: Binary search, insert/delete on heap or BST

O(N): linear
Running time increases directly proportional to growth of N. When N doubles, so does running time.

O(N log N): linearithmic
When N doubles, the running time slightly more than doubles.
Example: Quicksort, mergesort

O(N²): quadratic
Acceptable for relatively small problems. When N doubles, the running time increases fourfold.

O(N³): cubic
Acceptable only for small problems. When N doubles, running time increases eightfold.

O(2^N): exponential
Not typically appropriate for practical use. When N doubles, the running time squares.

O(N!): factorial
When N increases by 1, running time increases by a factor of N.