Big O and algorithm analysis

The big picture: what do we measure?

When you ask 'how fast is this program?', the answer in seconds is not very useful. A fast computer and a slow computer give different seconds for the same program. So we count something that does not change: the number of basic steps (a comparison, an addition, reading one cell of memory) as a function of the input size, which we call n.

Two kinds of cost

Words you will meet

• Input size (n): how much data the algorithm receives, for example the number of items in a list.
• [[Asymptotic|what happens when n becomes very, very large]]: we look at the big picture for huge inputs and ignore small details.
• Order of growth: the 'shape' of the growth, such as 'straight line' or 'curve that shoots up'.
• Worst, best and average case: the cost for the unluckiest input, the luckiest input, and a typical input.
• Lower bound: a limit saying 'no algorithm can do better than this'.

Growth of functions and their ordering

Different algorithms grow in different ways. Some barely notice a bigger input. Others explode. To compare them we use a small family of 'speeds', from the gentlest to the wildest.

The order is: 1 < log n < √n < n < n log n < n² < n³ < 2ⁿ < n! < nⁿ. A 'logarithm' grows very slowly: log₂ 1,024 is only 10, and log₂ 1,000,000 is only about 20.

What happens when the input doubles?

Two useful facts for comparing. First, polynomial growth (a power of n, like n² or n^1.5) always loses against exponential growth (2ⁿ) for big n. Second, a power of log n, even (log n)¹⁰, always loses against a small power of n like √n for big n. So n log n is smaller than n^1.5, because log n grows more slowly than √n. And n / log n is smaller than n, but larger than √n.

A faster computer helps less than you think. If an algorithm does n² operations and today it solves n = 1,000 in one second, a machine 100 times faster solves only n = 10,000 in that second (because 10,000² = 100 × 1,000²). The same speed-up on a 2ⁿ algorithm adds only about 7 to n.

Asymptotic notation: O, Ω, Θ, o, ω

Suppose an algorithm does exactly 3n² + 10n + 5 steps. For a huge n, the 10n and the 5 are tiny compared with 3n², and the 3 only depends on the computer. So we say the algorithm is 'of order n²'. The notations below give a precise way to say that.

The formal definition (for non-negative functions)

f(n) = O(g(n)) means: there are constants c > 0 and n0 such that f(n) ≤ c · g(n) for every n ≥ n0. In words: after some point, f never goes above a constant multiple of g. Ω is the same with ≥. Θ needs both: f = Θ(g) exactly when f = O(g) and f = Ω(g).

Example: to show 100n + 50 = O(n), take c = 150 and n0 = 1. For n ≥ 1 we have 100n + 50 ≤ 100n + 50n = 150n. Another valid pair is c = 101 and n0 = 50. Any pair that works proves the statement.

With limits it is even easier. Look at the ratio f(n)/g(n) when n goes to infinity. If it tends to 0, then f = o(g). If it tends to infinity, then f = ω(g). If it tends to a positive constant (for example 7), then f = Θ(g).

ratio f(n)/g(n) when n -> infinity

  0               ->  f = o(g)     (f is smaller)
  constant > 0    ->  f = Θ(g)     (same rate)
  infinity        ->  f = ω(g)     (f is bigger)

Useful facts

• n = O(n²) is true. O is only an upper bound, it does not need to be tight. It is like saying 'I am less than 100 years old'.
• Ω alone says nothing about an upper bound. 'This takes at least n steps' could be n or 1,000,000 n.
• 2^(n+1) = Θ(2ⁿ), because 2^(n+1) = 2 · 2ⁿ is only a constant factor bigger. But 2^(2n) = 4ⁿ = ω(2ⁿ), because the ratio 2ⁿ goes to infinity.
• The base of a logarithm does not matter inside O. log₂ n and log₁₀ n differ by a constant factor, so we just write O(log n).
• Θ is symmetric: if f = Θ(g), then g = Θ(f). O is not: n = O(n²), but n² is not O(n).
• log₂(n!) = Θ(n log n). This sum of logarithms is the tight order of growth of the logarithm of a factorial.
• Some pairs of functions are not comparable. If f(n) = n and g(n) is 1 for even n but n² for odd n, then f is neither O(g) nor Ω(g).

Counting operations in loops

To find the Big O of a program, we count how many times its main line runs as a function of n. A few rules solve almost every case.

• One after the other: add. Two loops one after the other, each with n steps, cost n + n = 2n, which is Θ(n).
• One inside the other: multiply. A loop of n steps containing another loop of n steps costs n × n = n².
• Drop constants and smaller terms. n² + n is Θ(n²).
• An if / else: take the worst branch when you do not know which one will be used.

Single loops and nested loops

// EN: A loop that runs n times does n steps: Θ(n).
for (let i = 0; i < n; i++) work();

// EN: Each pair (i, j) with i < j is visited once: n(n-1)/2 times, so Θ(n²).
// For n = 10 that is 10 * 9 / 2 = 45 times.
for (let i = 0; i < n; i++)
	for (let j = i + 1; j < n; j++) work();

Counting pairs is like counting handshakes in a room of n people: every pair shakes hands once, so there are n(n-1)/2 handshakes. Counting triples i < j < k works the same way: n(n-1)(n-2)/6 triples. For n = 6 that is 20. This is Θ(n³).

Loops that double or step by a changing amount

// EN: i doubles: 1, 2, 4, 8... only about log2(n) iterations: Θ(log n).
for (let i = 1; i < n; i *= 2) work();

// EN: Outer i doubles, inner runs i times: 1 + 2 + 4 + ... + n is about 2n: Θ(n).
for (let i = 1; i < n; i *= 2)
	for (let j = 0; j < i; j++) work();

// EN: Inner loop jumps by i: n/1 + n/2 + n/3 + ... is about n log n: Θ(n log n).
for (let i = 1; i <= n; i++)
	for (let j = 0; j < n; j += i) work();

The middle example is a geometric sum: each term is double the one before, so the whole sum is about twice the last term. The last example is a harmonic sum: n/1 + n/2 + ... + n/n, which is n times about ln n.

The cost depends on the value, not only on the length

A simple primality test tries divisors d = 2, 3, 4... while d × d ≤ n. In the worst case it makes about √n divisions, where n is the value being tested. That looks gentle, but a number with 100 digits has a value around 10¹⁰⁰, so √n is 10⁵⁰: far too many. Measured against the number of digits, the cost is exponential.

Best, worst and average case

The same algorithm can behave very differently depending on the data it receives. Looking for a name in a list of n names: if it is the first one you are lucky, if it is the last one (or missing) you are unlucky.

The worst case is the one we use most, because it is a promise: 'it will never be slower than this'. The average case needs an extra assumption that the worst case does not: a probability distribution of the inputs (for example, 'all positions are equally likely'). Without that assumption, 'average' means nothing.

Insertion sort

Insertion sort puts each new card in its place among the cards you already hold. On an already sorted list each card needs only one comparison: best case Θ(n). On a reversed list each card must pass all the previous ones: worst case Θ(n²).

Quicksort and its pivot

Quicksort picks a pivot, puts smaller items on one side and bigger on the other, and repeats on each side. If the pivot is always the first element, an already sorted (or reversed) list is the worst case: the pivot is the smallest item, one side is empty and the other has n - 1 items. The work is n + (n-1) + (n-2) + ... = Θ(n²).

With a random pivot, no particular input is bad any more. The bad luck now comes from the random choice, not from the data. The expected time is Θ(n log n) for every input. Bad pivots can still happen, but they are rare.

sorted list, pivot = first element:

[1 2 3 4 5]   pivot 1 -> left: []     right: [2 3 4 5]
[2 3 4 5]     pivot 2 -> left: []     right: [3 4 5]
[3 4 5]       pivot 3 -> left: []     right: [4 5]
...
n levels, each one doing about n work -> Θ(n²)

Recurrences and the master theorem

Some algorithms solve a problem by solving smaller copies of the same problem. This is called recursion. To measure them we write an equation that says: 'the cost of size n equals the cost of the smaller pieces plus the extra work'. This equation is a recurrence.

Writing the recurrences you need

For T(n) = T(n-1) + n with T(1) = 1, the values are T(2) = 3, T(3) = 6, T(4) = 10, T(5) = 15. It is the sum 1 + 2 + ... + n = n(n+1)/2. In Hanoi, to move n disks you move n-1 disks, move the biggest disk, and move the n-1 disks again, so the work doubles with every extra disk: T(n) = 2ⁿ - 1.

The master theorem

Many divide-and-conquer recurrences look like T(n) = a · T(n/b) + f(n). Here a is the number of recursive calls, n/b is the size of each call, and f(n) is the extra work outside the calls (splitting and merging). Compare f(n) with the number n^(log_b a), which is how much work the 'leaves' of the recursion do.

'Polynomially' means by a factor of at least n^ε for some ε > 0. Examples: T(n) = 2T(n/2) + n: here n^(log₂ 2) = n and f = n, a tie, so Θ(n log n). T(n) = 4T(n/2) + n: n^(log₂ 4) = n² beats n, so Θ(n²). T(n) = T(n/2) + n: n^(log₂ 1) = 1, f = n is bigger, so Θ(n). Strassen: T(n) = 7T(n/2) + n²: n^(log₂ 7) is about n^2.81, which beats n², so Θ(n^(log₂ 7)).

T(n) = 2T(n/2) + n

depth 0:      [ n ]                       -> n
depth 1:   [n/2]   [n/2]                  -> n
depth 2: [n/4][n/4][n/4][n/4]             -> n
...
depth i: 2^i nodes of size n/2^i          -> n

levels: log2(n)   total = n * log2(n)

The recursion tree shows why. At depth i there are 2^i nodes, each costing n / 2^i, so every level adds up to n. With about log n levels the total is n log n.

When the master theorem does not apply

• T(n) = T(n-1) + n and T(n) = 2T(n-1) + 1: the subproblem is n - 1, not n divided by something. Use the recursion tree, or expand and add.
• T(n) = 2T(n/2) + n log n: f(n) is bigger than n, but not polynomially bigger, so it falls between the three basic cases. An extended version gives Θ(n log² n).
• T(n) = T(n/3) + T(2n/3) + n: the two calls have different sizes. The recursion tree has about log n levels, each costing at most n, and the answer is Θ(n log n).

Proving by substitution

Another method is to guess the answer and prove it by induction. Careful: you must prove exactly the statement you guessed. If you assume T(n/2) ≤ c · n/2 for T(n) = 2T(n/2) + n, you get T(n) ≤ cn + n. That is not ≤ cn, so the proof of T(n) = O(n) fails (and indeed T(n) is Θ(n log n)). Concluding 'cn + n is O(n)' is a classic mistake, because the constant c must stay the same.

Loop invariants and proof of correctness

Being fast is useless if the answer is wrong. A loop invariant is a sentence about the variables that is true every time the loop starts a new round. It is a way of proving that an algorithm does the right thing.

The three steps

// EN: Invariant: when the test i < n runs, s is the sum of a[0..i-1].
// Start: i = 0, s = 0 (empty sum). Keep: adding a[i] gives the sum of a[0..i].
// End: i = n, so s is the sum of the whole array.
let s = 0;
for (let i = 0; i < a.length; i++) s += a[i];

Insertion sort has a famous invariant: at the start of the round that inserts a[j], the part a[0..j-1] holds the same elements as at the beginning, in sorted order. When j reaches n, the whole array is sorted.

A good invariant is strong enough

For a loop that computes the maximum with m = a[0], the sentence 'm equals some element of the array' is always true, but it is useless: at the end it does not say m is the largest. The right invariant is 'm is the largest of a[0..i-1]'. In termination, i = n and so m is the largest of the whole array.

Correct is not the same as finishing

An invariant proves that if the loop ends, the answer is right. You must also prove that the loop ends. In binary search, if lo = mid + 1 is changed to lo = mid, the invariant 'if x is in the array it is in a[lo..hi]' is still true, but when hi = lo + 1 the value of mid does not change and the loop runs forever. To prove termination, show a quantity that gets smaller each round and cannot go below a limit (here, hi - lo).

Amortised analysis

Some operations are cheap most of the time and expensive once in a while. If we only looked at the worst single operation we would be too pessimistic. Amortised analysis gives the average cost of an operation over a whole sequence of operations in the worst case. No probability is involved: it is a guarantee about the sequence.

The dynamic array that doubles

A dynamic array has some capacity. Appending to a full array is expensive because all elements are copied to a new array of double the capacity. Starting with capacity 1, after 16 appends the copies were 1 + 2 + 4 + 8 = 15 in total (the 17th append would copy 16 more). The sum of the copies is always less than 2n, so each append costs O(1) amortised.

capacity:  1   2   4       8               16
append #:  1   2  3 4,5 ... 8,9 ....... 16,17
copies:    -   1   2   4              8      (grow when full)

total copies after 16 appends = 1 + 2 + 4 + 8 = 15

If instead we grow by a fixed amount (say +100 slots), the copies are n + (n-100) + (n-200) + ... which is about n²/200 in total. That is Θ(n²) for n appends, so each append costs O(n) amortised. Doubling (growing by a factor) is what makes it O(1).

The binary counter

A binary counter flips bits when it increments. The lowest bit flips every time, the next every 2 increments, the next every 4... For a 5-bit counter incremented 16 times the flips are 16 + 8 + 4 + 2 + 1 = 31, less than 2 per increment. So an increment costs O(1) amortised, even though one increment can flip all the bits.

Methods

• Aggregate method: add up the cost of all n operations and divide by n (what we did above).
• Accounting (banker's) method: charge each operation a fixed price. Cheap operations are charged more than they cost, and the extra goes into a bank as credit. Expensive operations are paid for with the credit. The bank must never go negative.
• Potential method: a more formal version of the same idea, with a 'potential energy' stored in the data structure.

The lower bound of comparison sorting

Until now we looked for faster algorithms. Now we ask: is there a speed limit that no sorting algorithm can beat? For algorithms that sort by comparing two items at a time (like merge sort, quicksort and heap sort), the answer is yes: Ω(n log n).

The decision tree

Draw every comparison the algorithm makes as a branch: 'is a < b?' goes left for yes and right for no. Each path from the root to a leaf is one run of the algorithm, and the leaf says which order was found. For n distinct items there are n! possible orders, and every one must appear as a leaf. So the tree has at least n! leaves.

sorting 3 items a, b, c  (3! = 6 orders = 6 leaves)

            a < b ?
          /         \
     b < c ?       a < c ?
     /     \       /     \
  abc    a<c?    bac    b<c?
         /  \           /  \
       acb  cab       bca  cba

A binary tree of height h has at most 2^h leaves. So 2^h ≥ n!, and the height satisfies h ≥ log₂(n!). The height is the number of comparisons in the worst case. And log₂(n!) = Θ(n log n). Therefore any comparison sort needs Ω(n log n) comparisons in the worst case.

For 4 items: 4! = 24 orders, and 2⁴ = 16 < 24 ≤ 32 = 2⁵, so at least 5 comparisons are needed. For 5 items: 5! = 120 > 2⁶ = 64, so nobody can sort 5 items with 6 comparisons in the worst case: such a claim cannot be true.

How can some sorts be faster?

The bound applies only to sorts that learn about the data by comparing. Sorts that use the values themselves escape it:

They do not contradict the bound because they never ask 'is a < b?'. They use the value as an index in a table. The price: the range k must be small, and they only work for things like integers or short keys.

Space complexity

Time is not the only thing that costs. An algorithm also uses memory. Space complexity measures the memory an algorithm needs as the input grows. We usually count the auxiliary space: the extra memory used on top of the input itself.

O(1) auxiliary space means a fixed number of extra variables, not growing with n. Careful: 'in place' with recursion still uses space, because every call that has not finished is kept in the call stack. If a function calls itself n times in a chain, the stack holds n calls: O(n).

// EN: Each call waits for the next one, so n frames pile up: O(n) space.
// (Without tail-call optimisation, which most languages do not guarantee.)
function sum(n: number): number {
	if (n === 0) return 0;
	return n + sum(n - 1);
}

Quicksort partitions in place, but it recurses on both sides. If the pivot is always the worst one, the chain of calls is n deep, so the stack is O(n). Fibonacci with two calls makes an exponential number of calls in total, but at any single moment only one path from the root is open, at most n calls deep, so the stack is O(n).

There is also a link with time. If every step touches a constant number of memory cells, an algorithm cannot use more cells than it has steps. So S(n) = O(T(n)): the space is never bigger than the time. The opposite is false: an algorithm can take a lot of time using almost no memory.

Complexity of common data structure operations

Choosing a data structure is choosing which operations are cheap. Here are the costs you should know, with n elements.

Let us see why some of these hold.

Arrays and linked lists

An array keeps items side by side, so position i is found by simple arithmetic: O(1). But inserting at the beginning pushes every item one place to the right: O(n). A linked list is a chain of boxes, each pointing to the next, so inserting at the beginning only changes one pointer: O(1). To reach the i-th box you have to walk the chain: O(n).

Hash tables

A hash table with a good hash function and a controlled load factor (items per drawer) finds a key in O(1) on average. With chaining (each drawer holds a list), if every key falls into the same drawer, the lookup walks one list of n keys: O(n) in the worst case.

Trees and heaps

A binary search tree keeps smaller keys on the left and bigger on the right. If you insert 1, 2, 3, ..., n in order into a plain tree with no balancing, every key goes to the right, and the tree becomes a list: searching for n costs O(n). A balanced tree (AVL, red-black) repairs itself and keeps the height at O(log n), so it gives O(log n) search, insert and remove in the worst case, and an in-order walk lists the keys sorted in O(n). A hash table cannot list keys in order, so only the balanced tree meets all these requirements.

A binary min-heap keeps the smallest item at the root: reading it is O(1), removing it is O(log n) (move the last item to the root and let it sink). Building a heap from an arbitrary array with sift-down from the last internal node up to the root costs only O(n), not O(n log n), because most nodes are near the bottom and sink very little.

A queue on an array

If a queue is an array, enqueue writes at the end (O(1) amortised) but dequeue removes index 0 and shifts all the others: O(n). For n enqueues and n dequeues the total is O(n²). A linked list, or an array with two indices that move (a circular buffer), brings each operation to O(1).

P, NP and intractability

So far every algorithm we saw is 'fast enough'. But some problems seem to have no fast algorithm at all. To talk about them, computer scientists sort problems into classes.

Polynomial and non-polynomial

An algorithm runs in polynomial time if its cost is bounded by n raised to a fixed power: n, n log n, n², n³⁰⁰... Algorithms like 2ⁿ or n! are not polynomial (they are exponential or worse). Even n^(log n) is not polynomial. Polynomial algorithms are called tractable (manageable). The others are intractable for big inputs: even a computer a million times faster does not rescue 2ⁿ.

The classes

     +--------------------------+
     |           NP             |
     |    +----------+          |
     |    |    P     |   NP-    |
     |    |          | complete |
     |    +----------+          |
     +--------------------------+

  P is inside NP.  Is P = NP?  Nobody knows.

Facts you need

• P ⊆ NP: if you can solve a problem fast, you can also check an answer fast.
• P = NP is an open question. Nobody has proved it, and nobody has proved the opposite. Most experts believe P ≠ NP, but this is a belief, not a theorem.
• A decision problem has a yes/no answer. The travelling salesman decision version asks: 'is there a tour visiting all n cities once and returning to the start with cost at most K?'. It is in NP because, given a tour, you check in polynomial time that it visits every city once and that the cost is at most K.
• If anyone finds a polynomial algorithm for one NP-complete problem (such as SAT, the satisfiability of logic formulas), then every problem in NP has one, and P = NP.
• To prove a new problem X is NP-hard, take a problem A already known to be NP-complete and build a polynomial-time reduction from A to X: a fast way to turn any instance of A into an instance of X with the same answer. If X were easy, A would be easy.

Note the direction of the reduction: you reduce the known hard problem to the new one. Doing it backwards (new problem to known problem) would only show that the new problem is not harder than A, which proves nothing about its hardness.

Putting it all together

All the tools of this area answer one question: how does the cost of an algorithm grow with the size of the input? Here is how the pieces connect.

Common mistakes

• Thinking that Big O gives time in seconds. It gives the shape of growth.
• Confusing the best, worst and average case with the notations O, Ω and Θ.
• Saying Θ when you only proved O.
• Forgetting to drop constants and smaller terms, or dropping a term that matters (for example inside an exponent).
• Ignoring the memory used by recursion.
• Using the master theorem when the recurrence does not have the form a · T(n/b) + f(n).
• Believing that a faster computer changes the order of growth.
• Reading NP as 'not polynomial'.