Big O notation

The letter "O" in big O notation stands for order, in recognition that rates of growth are defined as the order of a function. We say that one function T(n) is a big O of another function, F(n), and we define this as follows:

The function, g(n), of the input size, n, is based on the observation that for all sufficiently large values of n, g(n) is bounded above by a constant multiple of f(n). The objective is to find the smallest rate of growth that is less than or equal to f(n). We only care what happens at higher values of n. The variable n₀represents the threshold below which the rate of growth is not important, The function T(n) represents the tight upper bound F(n). In the following plot we see that T(n) = n² + 500 = O(n²) with C = 2 and n₀ is approximately 23:

You will also see the notation f(n) = O(g(n)). This describes the fact that O(g(n)) is really a set of functions that include all functions with the same or smaller rates of growth than f(n). For example, O(n²) also includes the functions O(n), O(nlogn), and so on.

In the following table, we list the most common growth rates in order from lowest to highest. We sometimes call these growth rates the time complexity of a function, or the complexity class of a function: