The big O notation – summary
Big O notation was invented to describe the growth rate of a function. You basically take away all constants and small factors and only focus on the big factors. Let’s take an example; the function:
x^2 + 2x + 6
in terms of big O notation becomes:
O(x^2)
We use this notation to describe how algorithm costs grow with input size. For example, testing all distinct pairs of objects takes O(n²) time. The exact number of tests is n(n − 1) / 2, which is 4,950 for 100 objects.
An O(n log n) algorithm grows more slowly than a quadratic one, although constant factors and input size also affect actual performance. For illustration, at n = 100 the function n² gives 10,000, while n log₁₀ n gives 200. Big O describes growth rates rather than these exact counts; changing the logarithm's base changes only a constant factor.
The plot compares these two growth functions. Its horizontal axis is the number of items and its vertical axis is the function value.
As you can see, when the number of items increases, the number of checks to perform increases much more rapidly in the n^2 function than the n*log(n) function.
Here is a table of the most commonly used notations:
| Notation | Name |
|---|---|
| O(1) | Constant |
| O(log n) | Logarithmic |
| O(n) | Linear |
| O(n log n) | Linearithmic |
| O(n^2) | Quadratic |
You can find a more complete list in this Wikipedia article.