Lesson 3 of 4 — Running time
Counting Steps
A run of a program costs a number of steps. A program costs a function: the worst case at every input size. Big-O is what we say about that function, and nothing else. This is the fifth week of my data-structures course, rebuilt so that every claim in it is something you count, plot, or play against an opponent.
Trace one run
Pick a program and an input, then step or run. Each elementary step lights its line and adds one to that line's count.One run
Fix a program P and an input x. The running time of that one run, T(P, x), is the number of mechanical moves the machine needs to finish. Nobody counts mechanical moves for a real program, so we count elementary steps instead: one assignment, one comparison, one arithmetic operation, one array access, one return. Each takes a fixed amount of time on a given machine, regardless of the input, which is what makes the shortcut honest: changing what counts as one step (is i = i + 1 one step or two?) changes the count by at most a constant factor, and the descriptions we care about cannot see constant factors. Changing the machine itself can cost more: a Turing machine with a single tape needs about n2 moves to check that a word of length n is a palindrome, a job a program does in about n steps. So a running time is always a running time on some model, and this lesson’s model is elementary steps.
The bench above does this for a search: given a list A and a target t, it walks the list and returns whether t is there. The table under it is the count of one run, line by line.
Exercise bank
Four kinds of exercise, checked on the spot. A solved card stays solved but keeps working.
From one run to the program
The running time of a computation is a number. The running time of a program is a function, built from those numbers one input size at a time:
One dot per input of size n; the function is the top of each column. “Running time” with no adjective always means this worst case. The function is usually ugly except for toy examples, which is why it is described with big-O, Θ, or Ω — and those three are statements about functions, not about programs, and certainly not about cases.
Size, not value
“x has size n” means x occupies n memory locations. For a list or a string, size is its length. For a single number v, size is the number of bits needed to store it, ⌊log2 v⌋ + 1. Why the different treatment? Think of school addition as a program and yourself as the machine: you memorised the one-digit sums, those are your elementary steps, and adding an s-digit number to a t-digit number costs about max{s, t} of them. Linear in the sizes.
Now suppose your teacher promised you would never add more than five digits to five digits. The work is bounded by a constant, whatever the numbers are. Computers live under that promise: values fit in a 64-bit word, so +, × and comparisons cost a fixed amount each — the word-size convenience. The same convenience says [1, 2, 3] and [888, 99, 100000] have the same size: three words, two commas, two brackets.
The definition is a game
Here is the definition this lesson has been circling. Let 𝓕 be the functions from ℕ to ℝ. For g ∈ 𝓕,
and for nonnegative f, g: f ∈ Ω(g) iff g ∈ O(f), and f ∈ Θ(g) iff both. If you have played the Quantifier Gym, you know what to do with a sentence like this. It is a game: ∃loïse defends the claim by choosing c and n0; ∀bélard attacks by choosing an n beyond n0 where the inequality fails. The claim is true exactly when ∃loïse has a move that ∀bélard cannot answer.
Recursive programs
For a recursive program the running-time function satisfies a recurrence with the shape of the code. Factorial checks n == 0, multiplies, and calls itself on n − 1: T(n) = 2 + T(n − 1), with T(0) = 2 for the check and the return. Unwind it a few times, guess the pattern, prove it by induction. Then look again at what n was measuring.