Algorithms

What an algorithm is, exactly

A problem is a contract between input and output. An algorithm is one way of honouring it, and correctness means honouring it on every input, not on the ones you tried.

Counting steps: pseudocode and the machine we pretend to have

Before you can say one algorithm costs less than another, you have to agree what one step costs. That agreement is called a cost model.

Proving a loop right: the invariant

A sentence that is true before the loop, stays true through every pass, and says something useful when the loop stops.

Proving a recursion right: induction

Assume the smaller calls are already right, show the step is right, and check that the input really is getting smaller.

T(n): best case, worst case, average case

The same procedure on two inputs of the same size can do wildly different amounts of work, so cost is not one number but three.

O, Omega and Theta, defined properly

Three statements about how one function compares with another once n is large enough, each with two constants you have to be able to produce.

Working with the notation

The equals sign is not equals, a Theta inside a formula means something specific, and two functions need not be comparable at all.

Proving a cost cannot be beaten: lower bounds

An upper bound is a promise about every input. A worst-case lower bound needs only one bad input for each size, and finding that family is a skill of its own.

The ladder of growth rates

Constant, logarithmic, linear, n log n, polynomial, exponential and factorial, plus the two odd ones that turn up in real analysis.

Reading the constraints backwards

The largest input a problem allows is a message about which technique is expected. Learn to read it before you write anything.

Space, in-place work, and the cost of recursion

Memory is the second budget, and a recursion spends it invisibly, one stack frame per call.

Measuring growth on a real machine

Double the input, watch what the time does, and read the exponent straight off the ratio.

Worst case, amortised, expected: three different promises

All three get quoted as though they were the same guarantee. They are not, and the difference decides whether a system misses a deadline.

Name the brute force before you optimise anything

Write the obvious solution, cost it against the constraint, and if it does not fit, name the one line that is doing all the work.

How hard did the scanner work?

Coding problem · Counting operations, Best and worst case

Moves to tidy a bookshelf

Coding problem · Insertion sort, Worst case

What fits in the budget?

Coding problem · Growth classes, Reading constraints

Peak memory from an allocation log

Coding problem · Space complexity, Auxiliary space

Rebinding the photo album

Coding problem · Amortised cost, Growable arrays

Reading an exponent off a doubling experiment

Coding problem · Empirical analysis, Order of growth

Constants, sums and growths, worked on paper

Coding problem · Asymptotic notation, Summations, Growth rates