Big O

Below are six code fragments, each in Python and in Go. Guess how their running time grows as n grows, then see what a measurement on this site's server showed. A hint: in two fragments the answer depends on the language. Switch the language and find out which.

The trickiest are the third and fourth fragments. The code is the same, the growth differs: a string appended to one character at a time is quietly extended in place by Python, while Go copies it whole every time; a Python list whose first element is removed shifts its whole tail, while a Go slice only moves the start of its window. You cannot see this from the program text; you have to know what stands behind each operation. That is what the whole article is about: how to describe growth with one formula, and how not to go wrong when deriving it.

The idea

Measuring algorithms in seconds is awkward: seconds depend on the machine, the language and the data. But you can almost always say how the number of steps grows as the input size n grows: linearly, as a square, as a logarithm. The notation f(n) = O(g(n)) means that from some n on, f grows no faster than g, up to a constant factor.

The two parameters in the definition are two concessions. The factor c lets us ignore the constant cost of a step: it is smaller on a fast machine and larger on a slow one, but the growth is the same. The index n₀ lets us ignore small inputs: what matters is what happens when there is a lot of data. Try picking c and n₀ yourself:

For 3n² + 50n + 400, for example, c = 4 and n₀ = 58 work: for n ≥ 58 the lower terms 50n + 400 are at most n², and the whole sum is at most 4n². Hence the rule: only the highest power of a polynomial matters. The third pair teaches something else: n log n + 1000n = O(n log n), but the factor needed is huge, since the lower term 1000n is caught up by n log₂ n only at n = 2¹⁰⁰⁰. Formally the constant does not matter; in practice it decides everything. And the fourth pair is an example of the definition failing: n² is not O(n log n). The ratio n²/(n log n) = n/log n grows without bound, and for any c there is an n where n² is greater than c·n log n.

O, Ω and Θ

O is only an upper bound. Formally it is true that 5n = O(n²): a linear function grows no faster than a quadratic one. To say something sharper, two more symbols are needed:

• Ω is a lower bound: f = Ω(g) if f(n) ≥ c·g(n) for some c > 0 and all large n. Any comparison sort makes Ω(n log n) comparisons in the worst case; this is proved in the article on the lower bound.
• Θ is a tight bound: f = Θ(g) if both f = O(g) and f = Ω(g). Merge sort runs in Θ(n log n) on any input.

In conversation and in documentation people write O and almost always mean Θ: “dictionary lookup is O(1)” means “no longer than a constant, and no faster”. That is harmless as long as you remember the difference. One more subtlety: O says nothing about which case is meant. Quicksort has a worst case of Θ(n²) and an average of Θ(n log n); for a dynamic array one append costs Θ(n), while on average over any sequence it is O(1) amortized. When talking about complexity, say which: the worst case, the average or the amortized.

How to estimate code

For most programs a few rules are enough:

• Consecutive parts add up, and the larger one remains: O(n) + O(n log n) = O(n log n). Sorting and then a linear pass is O(n log n).
• Nested loops multiply if the number of steps of the inner one does not depend on the outer: two loops over n are O(n²).
• If it does depend, compute the sum. The loop for j in range(i) inside a loop over i makes 0 + 1 + … + (n − 1) = n(n − 1)/2 steps: a square as well. But the loop with step i from the fifth fragment makes n/1 + n/2 + … + n/n ≈ n ln n: two nested loops, and no square.
• A loop that halves the size makes log₂ n steps. The base of the logarithm is not written in O: log₂ n and log₁₀ n differ by a constant factor, log₂ 10 ≈ 3.32.
• Recursion gives an equation. Merge sort: T(n) = 2T(n/2) + n, which gives n log n; such equations are solved by the master theorem. Naive Fibonacci numbers: T(n) = T(n − 1) + T(n − 2) + 1 grows like the Fibonacci numbers themselves, that is, like 1.618ⁿ.
• A library call is not one step. x in list, list.pop(0), list.insert(0, x), the slice a[1:] in Python, slices.Contains and s += "x" in Go are all O(n). The complexity of every operation is worth knowing for your language; the quiz above is about that.

If deriving the formula is hard, there is a simple check, the doubling test. Run the program on n and on 2n and see how many times the work grew. If it grows as n^k, the ratio will be 2^k, and k = log₂ of the ratio. It is most reliable to count steps rather than time:

Code

The triangular loop gives 2.00 on the nose, the triple one 2.99. Halving gives 0.07: doubling n adds only one step to a logarithm. But n log n shows 1.08, almost indistinguishable from linear growth by doubling; the difference shows only if n grows by many orders of magnitude. For an exponential, doubling makes no sense, and one looks at the step n → n + 1: the number of calls of naive Fibonacci grows by a factor of 1.618, the golden ratio.

With time instead of steps it is all the same, only noisy. Here is a measurement of all six quiz fragments: on logarithmic axes the slope of a line is the growth exponent.

What O does not tell you

Asymptotics compare algorithms on very large inputs and say nothing about the rest. This is what they hide:

• The constant. 1000·n log₂ n is larger than n² for any n up to about fourteen thousand: an asymptotically better algorithm loses while the data are few. That is why library sorts finish off small pieces with insertion sort: on ten elements a quadratic algorithm with a tiny constant is faster.
• Memory. A hash table lookup is O(1), but on a million keys it is several times more expensive than on a thousand: a large table does not fit in the processor cache. You can see this in the quiz on the set lookup and in the article on the hash table.
• What the inputs are like. The worst case may never occur, or it may come from an adversary, like the quicksort killer.
• How much that is in seconds. To turn steps into seconds you need the speed of the language and the machine; that is the subject of the article “How many operations per second”.

The estimate itself costs nothing: it is done in your head, from the program text. And it almost always answers the main question: whether the work grows so that, with ten times more data, the program slows down ten times, a hundred times or a thousand.

History

The O symbol was invented by mathematicians long before computers. Paul Bachmann introduced it in 1894 in a book on analytic number theory, to write about the order of magnitude of an error, and Edmund Landau made it familiar in 1909, which is why O, o and their relatives are called Landau symbols. They began to be applied to the number of steps of programs in the 1960s: in 1965 Juris Hartmanis and Richard Stearns, in the paper “On the computational complexity of algorithms”, proposed measuring problems by how the running time grows with the length of the input, and in 1993 they received the Turing Award for it. Ω and Θ in their present sense were fixed by Donald Knuth in 1976 in the note “Big Omicron and big Omega and big Theta”, proposing that everyone write them the same way.

Problem

The fifth fragment of the quiz, but with n up to 10¹¹. The answer is how many times the inner line runs; first estimate how many steps that is, and it will become clear that running the program from the statement is useless.