Speak Maths · University

Big-O: how fast does the work grow?

Big-O notation compares how fast two quantities grow when n gets large, ignoring constant factors. It is how computer scientists say that one method is hopelessly slower than another.

Draft: written by an AI helper and not yet checked by a teacher.

The alphabet

Read each sign aloud, the way it is written under it.

$f (n) = O (g (n))$ Say: f of n is big-O of g of nMeans: f grows no faster than g, up to a constant factor, once n is large.
$f (n) = Θ (g (n))$ Say: f of n is big-theta of g of nMeans: f and g grow at the same rate: f stays between two constant multiples of g.
$f (n) = Ω (g (n))$ Say: f of n is big-omega of g of nMeans: f grows at least as fast as g, up to a constant factor.
$f (n) = o (g (n))$ Say: f of n is little-o of g of nMeans: f becomes negligible next to g: the ratio of f to g tends to 0.
$f (n) \sim g (n)$ Say: f of n is asymptotic to g of nMeans: f and g are almost equal for large n: the ratio of f to g tends to 1.
$lo g_{2} n, n lo g_{2} n$ Say: log base two of n, and n times log base two of nMeans: The number of times n can be halved, and that number multiplied by n.
$2^{n}, n!$ Say: two to the n, and n factorialMeans: Two fast-growing kinds: doubling at every step, and multiplying by every number up to n.
$T (n) = 2 T (n /2) + n$ Say: T of n equals two times T of n over two, plus nMeans: A recurrence: the cost for size n is two jobs of half the size, plus n extra steps.

The story: Two ways to find a name

Subtitles:

Tap a line to see its words.

$T_{1} (n) = n \Rightarrow T_{1} (1 0^{6}) = 1 0^{6}$ Way one: look at the names one by one. In the worst case n looks; for a million names, a million looks.
$T_{2} (n) = ⌊ lo g_{2} n ⌋ + 1 \sim lo g_{2} n$ Way two, on a sorted list: look in the middle, throw away the wrong half, repeat. About log₂ n looks.
$2^{19} < 1 0^{6} < 2^{20} \Rightarrow T_{2} (1 0^{6}) = 20$ Since a million lies between 2¹⁹ and 2²⁰, the halving ends after exactly 20 looks.
$T_{1} (n) = Θ (n), T_{2} (n) = Θ (lo g n)$ One method grows like n, the other like log n; the constant does not matter.
$T_{2} (n) = O (T_{1} (n)), T_{1} (n) = Ω (T_{2} (n))$ Binary search is at most linear search up to a constant, and linear search is at least binary search.
$T_{2} (n) = o (T_{1} (n))$ Much more: the ratio of the fast cost to the slow cost tends to zero.
$n < n lo g_{2} n < n^{2} < 2^{n} < n! (n \geq 5)$ For n at least five the growth orders climb: n, n log n, n squared, 2ⁿ, n factorial.
$20! \approx 2.4 \times 1 0^{18}$ Trying every order of just 20 names means about 2.4 times ten to the eighteen orders: hopeless.
$T (n) = 2 T (n /2) + n$ Sorting by splitting: sort two halves, then merge them in n steps.
$T (n) = Θ (n lo g n)$ This recurrence solves to a cost of the order n log n, between linear and quadratic.

In words this story is 870 letters long; in symbols, 187.

Read it

What does it say?

$f (n) = O (n^{2})$

$f (n) = Θ (n)$

$f (n) = o (g (n))$

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

$f (n) = Ω (n lo g n)$

$n = o (n^{2})$

$2^{n} = Ω (n^{100})$

$lo g_{2} n$

$T (n) = T (n - 1) + 1$

$f (n) \sim n^{2} /2$

$n lo g_{2} n$

$f (n) = O (1)$

Write it

Which notation says this?

f grows at least as fast as g, up to a constant factor.

For large n, f and g are almost equal: their ratio tends to 1.

Binary search on a list of n items needs about log base two of n looks.

n log n grows no faster than n squared, up to a constant.

The costs of the two methods are of the same order.

Binary search: the cost for size n is the cost for half the size, plus one step.

Halving a million down to one takes about twenty steps.

Trying every order of n items costs of the order n factorial.

log n is negligible next to n.

The cost doubles whenever n goes up by one: exponential growth.

For large n the number of steps is almost exactly n squared over two.

Every method for this task needs at least of the order n log n steps.

Build it

Tap the tiles in order. One tile does not belong.

The cost T of n is of the same order as n log n.

The cost for size n is two costs for half the size, plus n.

The cost for size n is the cost for size n minus one, plus n more steps.

n is negligible next to n squared.

The ratio of f to g tends to 1: f and g are asymptotically equal.

Twenty factorial is about 2.4 times ten to the eighteenth.

Challenges

Creative puzzles that use every sign of this chapter. Take your time; there is no clock.

1 The ladder of growth

Six growth rates, each tested against each. Judge each sentence about them.

	$lo g n$	$n$	$n lo g n$	$n^{2}$	$2^{n}$	$n!$
$lo g n$	✓	✓	✓	✓	✓	✓
$n$		✓	✓	✓	✓	✓
$n lo g n$			✓	✓	✓	✓
$n^{2}$				✓	✓	✓
$2^{n}$					✓	✓
$n!$						✓

A tick means the row’s function is big-O of the column’s function.

$n lo g n = O (n^{2})$
$n^{2} = O (n lo g n)$
$\forall g : lo g n = O (g)$
$\exists f : f = o (lo g n)$
$2^{n} = Ω (n^{2})$
$\exists f : f = Θ (n) \land f = o (n^{2})$

2 Five relatives

Five comparisons of two growing functions. Pair each with what it says.

Tap a line, then its meaning.

3 The splitting cost

Sorting by splitting costs: two sorts of half the size, plus n steps to merge. One tile is wrong. Find it, then fix it.

Tap the tile that is wrong.

4 Smaller, truly smaller

This should say that n is negligible next to n log n. One tile is wrong. Find it, then fix it.

Tap the tile that is wrong.

5 Looks in a million

Binary search needs at most this many looks in a sorted list of a million names. What is the number?

$⌊ lo g_{2} 1 0^{6} ⌋ + 1 = ?$

6 Unroll it

With T(1) = 0, how large is T(8)?

$T (1) = 0, T (n) = 2 T (n /2) + n, T (8) = ?$

7 Doubling beats thousands

Doubling at every step: what is the smallest n for which 2ⁿ exceeds a thousand?

$min {n : 2^{n} > 1000} = ?$

8 Say who wins

T₁ is the cost of the slow way and T₂ the cost of the fast way. Write that the fast way’s cost is negligible next to the slow way’s.

Your version

9 What finishes in a second?

A fast computer does about a billion steps a second. Four costs (columns) at four input sizes (rows). The letter n runs over the four sizes. Judge each sentence in this grid.

	$n^{2}$	$2^{n}$	$n!$	$n lo g_{2} n$
$n = 10$	✓	✓	✓	✓
$n = 20$	✓	✓		✓
$n = 40$	✓			✓
$n = 1 0^{6}$				✓

A tick means that cost, at that n, is at most a billion steps: it finishes within about a second.

$\forall n : n lo g_{2} n \leq 1 0^{9}$
$\exists n : n^{2} > 1 0^{9} \land 2^{n} \leq 1 0^{9}$
$\exists n : 2^{n} \leq 1 0^{9} \land n! > 1 0^{9}$
$\forall n : n! \leq 1 0^{9} \Rightarrow 2^{n} \leq 1 0^{9}$
$\exists n : n^{2} > 2^{n}$
$\forall n : 2^{n} \leq 1 0^{9} \Rightarrow n^{2} \leq 1 0^{9}$

10 Almost equal

Six functions, each tested against each. The letters f and g run over the six. Judge each sentence about them.

	$n$	$n + 1$	$2 n$	$n^{2}$	$n^{2} + n$	$(n + 1)^{2}$
$n$	✓	✓
$n + 1$	✓	✓
$2 n$			✓
$n^{2}$				✓	✓	✓
$n^{2} + n$				✓	✓	✓
$(n + 1)^{2}$				✓	✓	✓

A tick means the row’s function is asymptotic to the column’s: their ratio tends to 1.

$n \sim n + 1$
$n \sim 2 n$
$2 n = Θ (n)$
$(n + 1)^{2} \sim n^{2}$
$n^{2} + n = o (n^{2})$
$\forall f \exists g \neq = f : f \sim g$

11 Five recurrences

Five ways a cost can depend on smaller cases. Pair each with the order it solves to.

Tap a line, then its meaning.

12 Doubling loses to factorial

This should say that 2 to the n is negligible next to n factorial. One tile is wrong. Find it, then fix it.

Tap the tile that is wrong.

13 Halving a million

This should say how many times a million can be halved before one item is left: about twenty. One tile is wrong. Find it, then fix it.

Tap the tile that is wrong.

14 Looks in a thousand

Binary search: one look, then the same job on half the list; a single item takes one look. How many looks for 1024 items?

$T (1) = 1, T (n) = T (n /2) + 1, T (1024) = ?$

15 Three claims, one true

Which of the three statements about this f is true?

$f (n) = 3 n^{2} + 100 n$

16 Comparing with everyone before

Placing each new card among the cards already sorted takes up to 1 + 2 + … + n comparisons. What order of growth is that sum?

$1 + 2 + \dots + n = \frac{n ( n + 1 )}{2} = Θ (?)$

17 Every pair

Checking every pair among n items for a clash costs about n squared over two checks: of the order n squared. Write it in notation, then compare.

Your version

18 Never gets harder

Looking up a word in a hash table costs about the same however many words are stored: the cost stays below some fixed bound. Write it in notation, then compare.

Your version

19 Say what big-O means

The definition: f is big-O of g when, beyond some starting point, f is never more than a fixed multiple of g. Write it with quantifiers, then compare.

Your version

Tell your own

Describe two ways to do one chore (find a card in a pile, tidy a shelf) with their costs in n, and say which is little-o of the other.

Kept on this device only.

Big-O: how fast does the work grow?

The alphabet

The story: Two ways to find a name

Read it

Write it

Build it

Challenges

1 The ladder of growth

2 Five relatives

3 The splitting cost

4 Smaller, truly smaller

5 Looks in a million

6 Unroll it

7 Doubling beats thousands

8 Say who wins

9 What finishes in a second?

10 Almost equal

11 Five recurrences

12 Doubling loses to factorial

13 Halving a million

14 Looks in a thousand

15 Three claims, one true

16 Comparing with everyone before

17 Every pair

18 Never gets harder

19 Say what big-O means

Tell your own

Download for offline use