Common Big-Oh Running Times
- O(1) or constant time: The holy grail of algorithms
is a program that takes the same amount of time regardless
of the problem size.
An example of O(1) time is table lookup,
where the table is represented by an array.
Any problem with a finite number of possible inputs can be solved
in O(1) time by simply looking up the answer in a pre-computed table.
- O(log n) or logarithmic time:
A divide-and-conquer technique that continually cuts the problem size
in half results in O(log n) running time.
Binary search is O(log n),
where n is the size of the lookup table.
- O(n) or linear time: Since most algorithms require that we look
at the entire input,
most algorithms require at least linear time,
so a linear time algorithm
is usually considered a terrific solution to a problem.
- O(n log n) or n log n time:
A divide-and-conquer algorithm that looks at the whole
input within each step
often produces results in O(n log n) time.
Efficient sorting algorithms (e.g. Heapsort) are
n log n worst-case; Quicksort is n log n time average case.
- O(n^2) or quadratic time: Doubly nested loops typically
result in programs that require quadratic time.
sorting algorithms, such as Bubblesort, require O(n^2) time.
- O(n^3) or cubic time: Triple-nested loops typically produce
programs that require cubic time.
- O(2^n) or exponential time: Algorithms that require exponential time
are essentially impractical except for the smallest inputs.
Some problems require exponential time (ie., there is
no efficient program for these problems), and thus are
not generally solvable by computer in any practical amount of time.