We write expressions like O(n) and O(n2) to describe the performance of algorithms. This is called “big-O” notation, and describes performance in a way that is largely independent of the kind of computer on which we are running our code. This is handy.
The statement that f(n) is O(g(n)) means that g(n) is an upper bound for f(n) within a constant factor, for large enough n. That is, there exists some k such that f(n) ≤ k·g(n) for sufficiently large n.
For example, the function f(n) = 3n−2 is O(n) because (3n−2) ≤ 3n for all n > 0. That is, the constant k is 3. Similarly, the function f'(n) = 3n + 2 is also O(n). It is bounded above by 4n for any n larger than 2. This shows that kg(n) doesn't have to be larger than f(n) for all n, just for sufficiently large n. That is, there must be some value n0 such that for all n ≥ n0, kg(n) is larger than f(n).
A perhaps surprising consequence of the definition of O(g(n)) is that both f and f' are also O(n2), because the quantity (3n±2) is bounded above by kn2 (for any k) as n grows large. In other words, big-O notation only establishes an upper bound on how the function grows.
A function that is O(n) is said to be asympotically linear and a function that is O(1) is said to be constant-time because it is always less than some constant k. A function that is O(n2) is called quadratic, and a function that is O(ny) for some positive integer y is said to be polynomial.
An expression like O(g(n)) is not a function. It really describes a set of functions: all functions for which the appropriate constant factor k can be found. For example, when we write O(10) = O(1) or O(n+1) = O(n), these are (true) statements about the equality of sets of functions. Sometimes people write “equations” like 5n+1 = O(n) that are not really equations. What is meant is that the function f(n) = 5n + 1 is in the set O(n). It is also a common shorthand to use mathematical operations on big-O expressions as if they were numbers. For example, we might write O(n) + O(n2) = O(n2) to mean that the sum of any two functions that are respectively asymptotically linear and asymptotically quadratic is asymptotically quadratic.
It helps to have some rules for reasoning about asymptotic complexity. Suppose f and g are both functions of n, and c is an arbitrary constant. Then using the shorthand notation of the previous paragraph, the following rules hold:
c = O(1)
O(c·f) = c·O(f) = O(f)
cnm = O(nk) if m ≤ k
O(f) + O(g) = O(f + g)
O(f)·O(g) = O(f·g)
logc n = O(log n)
However, we might expect that O(kn) = O(k'n) when k≠k', but this is not true when k > k'. In that case, the ratio k'n/kn grows without bound.
Together, the constants k and n0 form a witness to the asymptotic complexity of the function. To show that a function has a particular asymptotic complexity, the direct way to produce the necessary witness. For the example of the function f'(n) = 3n + 2, one witness is, as we saw above, the pair (k=3, n0=2). Witnesses are not unique. If (k, n0) is a witness, so is (k', n'0) whenever k'≥k and n'0≥n0.
Often, a simple way to show asymptotic complexity is to use the limit of the ratio f(n)/g(n) as n goes to infinity. If this ratio has a finite limit, then f(n) is O(g(n)). On the other hand, if the ratio limits to infinity, f(n) is not O(g(n)). (Both of these shortcuts can be proved using the definition of limits.)
To evaluate the limit of f(n)/g(n), L'Hôpital's rule often comes in handy. When both f(n) and g(n) go to infinity as n goes to infinity, the ratio of the two functions f(n)/g(n) limits to the same value as the limit of their derivatives: f'(n)/g'(n).
For example, lg n is O(n) because limn→∞ (lg n)/n = limn→∞ (1/n)/1 = 0. In turn, this means that lgk n is O(n) for any k because the derivative of lgk n is k/(n lgk-1 n). Since lg n is O(n), so is lg2 n, and therefore lg3 n, and so on for any positive k. (This is an argument by induction.)