MA0 2

Introduction to Algorithms and Numerical Analysis

Every lesson so far, in one document · 5 chapters

Lesson 3

Introduction to Python

Taught 02 Sept 2026

Imperative Knowledge and Computation

There are two kinds of knowledge a mathematical text can record. Declarative knowledge is a statement of fact: the square root of a positive real $x$ is the positive $y$ with $y^2 = x$ . Imperative knowledge is a recipe: a sequence of instructions which, followed to the letter, produces it. A machine can carry out imperative knowledge, but not declarative knowledge.

At its lowest level a computer does two things: it performs arithmetic, and it stores the results. It does billions of operations a second and can store a great deal.

Definition 3.1 (Algorithm).

An algorithm is a finite sequence of unambiguous instructions which, given an initial state and a set of inputs, passes through well-defined successive states and after finitely many steps produces an output and stops.

Finite rules out an infinite list of instructions. Unambiguous rules out a step whose meaning depends on who is reading it. After finitely many steps rules out a recipe that never returns an answer; of the three conditions it is the hardest to check.

Writing an algorithm down needs a notation for assignment, which has no counterpart in an equation. We write

g \defeq e

for the instruction “replace the current value of $g$ by the value of the expression $e$ ”. It is an instruction, not a statement about $g$ . The instruction $g \defeq g + 1$ makes sense, while the equation $g = g + 1$ has no solutions.

Here is Heron of Alexandria’s method for the square root of a real $x > 0$ .

Choose any guess $g > 0$ .
If $g^2$ is close enough to $x$ , stop and return $g$ .
Otherwise perform $g \defeq \tfrac{1}{2}\bigl(g + x/g\bigr)$ .
Go back to step 2.

Figure 3.1. Heron’s method as a flowchart. The test in the diamond decides which arrow is followed, and the arrow from the update box returns to the test, so the accented box may run any number of times.

The procedure has the two ingredients of every algorithm: a list of operations, and control flow, the rule deciding which operation comes next. Control flow depends on tests that answer yes or no, and it lets a fixed piece of text describe a computation whose length is not fixed.

Problem 3.1.

Let $x = 25$ and $g = 1$ , and read “close enough” as $|g^2 - x| < 0.01$ . Compute the first three values of $g$ produced by Heron’s method. Does the method stop within those three steps?

Computability

Early machines were fixed-program computers, wired to solve one problem. The stored-program computer keeps the instructions and the data they act on in the same memory, so that a single interpreter can execute any legal instruction sequence handed to it. A program counter walks the interpreter through the instructions in order, deviating only where control flow says to jump. Since the output of a computation may itself be a sequence of instructions, a machine of this kind can write its own programs.

Remark (The Church–Turing thesis).

Turing’s 1936 model, the Universal Turing Machine, is the standard formalisation of what a stored-program machine can do. The Church–Turing thesis asserts that a function is computable by any effective procedure exactly when some Turing machine computes it. It is not a theorem: “effective procedure” is an informal notion, and the thesis says that the formal model captures it.

A language is Turing complete if it can simulate a Universal Turing Machine. Python is, and so is every language in ordinary use, which is why any algorithm expressible in one of them is expressible in all of them.

There is, however, no algorithm which, given an arbitrary program and its input, decides in finitely many steps whether that program eventually stops or runs forever. This is the halting problem. Because it is unsolvable, the clause “stops after finitely many steps” in the definition of an algorithm has to be proved for each algorithm separately; it cannot be checked mechanically.

Syntax and Semantics

A program is a piece of text, and like a mathematical formula it has a meaning only if it obeys three kinds of rule.

Primitives. The atoms of the language: numeric literals such as 3.2, strings of text, and operators such as + and *.
Syntax. The rules saying which arrangements of primitives are well formed. 3.2 + 3.2 is well formed; 3.2 3.2 is not. Violations are caught before a single instruction runs.
Static semantics. The rules saying which well-formed arrangements have a meaning. Adding a number to a piece of text has the right shape, operand-operator-operand, and still means nothing.

A program that obeys all three has a semantics: exactly one meaning, fixed by the language and not by the reader. An English sentence, by contrast, can have several.

So when a program misbehaves the machine has not misunderstood it: the error is in what was written. It shows up in one of three ways: the program stops with an error, it runs forever, or it finishes and returns the wrong answer. The third gives no sign that anything is wrong, which is why a program needs a proof of correctness and not only a run that looked right.

Problem 3.2.

Classify each of the following as a syntax error, a static semantic error, or a program that runs to completion and returns the wrong answer. Justify each answer in a sentence.

x = 5 + * 3
x = "hello" + 7
An implementation of Heron’s method that stops as soon as $g^2 > x$ rather than when $|g^2 - x|$ is small.

Problems, Words and Languages

To compare algorithms for a problem, the problem has to be stated in a fixed form. A machine reads and writes finite strings of characters, so problems are stated in terms of strings.

Definition 3.2 (Alphabet, word and language).

Let $A$ be a non-empty finite set, called an alphabet. For $k \in \mathbb{N}_0$ let $A^k$ denote the set of functions $\{1, \ldots, k\} \to A$ . Such a function $f$ is written as the sequence

f(1)\,f(2)\cdots f(k)

and is called a word, or string, of length $k$ over $A$ . The set $A^0$ has a single element, the empty word, of length $0$ . Writing

A^{*} = \bigcup_{k \in \mathbb{N}_0} A^{k}

for the set of all words over $A$ , a language over $A$ is a subset of $A^{*}$ .

A set $S$ is finite if there is an injection $S \to \{1, \ldots, n\}$ for some $n \in \mathbb{N}$ , and infinite otherwise; the number of elements of a finite set is written $|S|$ . A set admitting an injection into $\mathbb{N}$ is countable, and the infinite ones among them are the countably infinite sets of the last lesson.

Definition 3.3 (Computational problem).

A computational problem is a relation $P \subseteq D \times E$ such that every $d \in D$ has at least one $e \in E$ with $(d, e) \in P$ . The elements of $D$ are the instances of $P$ , and $e$ is a correct output for the instance $d$ whenever $(d, e) \in P$ .

The problem is unique if $P$ is a function, so that every instance has exactly one correct output. It is discrete if $D$ and $E$ are languages over a finite alphabet, and numerical if $D \subseteq \mathbb{R}^m$ and $E \subseteq \mathbb{R}^n$ for some $m, n \in \mathbb{N}$ . A unique problem $P : D \to E$ with $|E| = 2$ is a decision problem.

A decision problem is one whose answer is yes or no, and we state such a problem by naming its instances and asking the question.

Example 3.4 (Primality as a decision problem).

Taking $\mathbb{N}$ as a language over the alphabet $\{0, 1, \ldots, 9\}$ , the relation

\bigl\{\, (n, e) \in \mathbb{N} \times \{0, 1\} \;\bigm|\; e = 1 \text{ exactly when } n \text{ is prime} \,\bigr\}

is a decision problem, which we write as

Primality
Input:    n ∈ N.
Question: is n prime?

A machine works directly only on discrete problems. A numerical problem must have its instances and its answers written as finite strings, and no finite string names an arbitrary real; rounding error is the difference between a real number and the string used for it.

Pseudocode

An algorithm does not depend on a programming language, and is usually written in pseudocode: the control flow and the assignments written out, without the details a particular language would require. An algorithm in pseudocode names its input and its output, and uses $\defeq$ for assignment and output for the result.

Example 3.5 (The square of an integer).

Squaring a natural number takes a single instruction, and the algorithm written out in full reads

The Square of an Integer
Input:  x ∈ N.
Output: the square of x.

    result ≝ x · x
    output result

The variables here are the input x and the working variable result; the assignment puts the value of $x \cdot x$ into result, and output yields what result holds.

We use pseudocode to describe an algorithm and Python to run it.

Objects and Types

A Python program is a sequence of definitions and commands, evaluated in order by an interpreter. A command is called a statement, and it instructs the interpreter to do something. A call to the built-in print writes to the screen: it takes any number of arguments, separates them by spaces, and follows them by a newline unless told otherwise.

print("Algorithm")
print("terminated.")

# several arguments, and a different ending
print("Algorithm", "terminated", end=".\n")

Writing an f before the opening quote of a string makes it an f-string, in which any expression placed in braces is evaluated and its value substituted:

n = 7
print(f"{n} squared is {n * n}")   # 7 squared is 49

In mathematics the legality of an operation depends on what it is applied to: addition is defined for numbers, composition for maps. In Python each value is an object, and every object has a type, which fixes the operations allowed on it. The interpreter uses types to enforce static semantics.

Types divide into scalar, meaning indivisible, and non-scalar, meaning having internal structure. Python has four primitive scalar types.

int, the integers, written as usual: 5, -12.
float, an approximation to the reals, written with a decimal point (3.0, -28.72) or in scientific notation (1.6e-19). Memory is finite and the reals are not, so a float holds one of finitely many values and float arithmetic is not the arithmetic of $\mathbb{R}$ : the expression 0.1 + 0.2 == 0.3 evaluates to False.
bool, inhabited by exactly two values, True and False.
None, inhabited by one value, used for the absence of a result.

Expressions and Relational Operators

Objects combined with operators according to the syntax form an expression, and every expression evaluates to a single object of some type. The built-in type reports which type an object has:

type(5)     # int
type(5.0)   # float

Control flow needs tests that come out True or False, and these are built with the relational operators <, <=, >, >=, == and !=. Every one of them evaluates to a bool.

Python’s notation differs from the pseudocode here. Mathematical assignment $g \defeq e$ is written in Python with a single equals sign, g = e. Testing whether two expressions have the same value is ==, and testing that they do not is !=.

3.0 + 2.0   # the float 5.0
3 != 2      # the bool True

Problem 3.3.

Give the value of type(4 == 4) and of type(4.0). Then say what happens if the test in step 2 of Heron’s method is written with = in place of ==, and which of the three kinds of rule of the previous section it breaks.

Arithmetic Operators

Addition, subtraction and multiplication are +, - and *, and exponentiation is **. Division splits into three operators, two of which are the floor and the remainder of the last lesson.

/ always evaluates to a float: 5 / 3 gives 1.6666666666666667.
// is floor division, the largest integer not exceeding the quotient. So 5 // 3 is 1 and -4 // 3 is -2.
% is the remainder: 5 % 3 is 2. A modern processor carries out % and // in a few clock cycles, so we count each of them as a single elementary operation.

Remark (Floors and remainders in Python).

For integers a and b > 0, a // b is $\lfloor a/b \rfloor$ and a % b is $a \bmod b$ as defined in Definition 2.19. The identity $z = b\lfloor z/b\rfloor + (z \bmod b)$ therefore reads

a == b * (a // b) + a % b

and holds for every integer a. It holds for negative a because // rounds down, not towards zero.

Problem 3.4.

Verify that a % b and a - (a // b) * b are equal, first for $b = 3$ and $a = 7, 6, 0, -1, -4$ , and then in general.

Suppose integer division were defined by truncation towards zero instead, so that $-4$ divided by $3$ gave $-1$ . What must the remainder then be for the identity to survive, and what happens to the guarantee $0 \leqslant a \bmod b < b$ ?

Compound expressions are read by precedence: ** binds most tightly, then *, /, // and %, then + and -.

print(2 + 3 * 4)   # 14, not 20
print(5 + 4 % 3)   # 6, not 0   (% binds as tightly as * and /)
print(2 ** 3 * 4)  # 32, not 4096

Operators of equal precedence are read by associativity. Most associate to the left; exponentiation associates to the right.

print(5 - 4 - 3)    # -2, not 4
print(4 ** 3 ** 2)  # 4 ** 9 = 262144, not 64 ** 2 = 4096
print((4 ** 3) ** 2)  # 4096

Logical Operators

The three logical connectives, negation, conjunction and disjunction, are implemented as the keywords not, and and or. They act on bool values and are fixed by these tables, in which T and F abbreviate True and False.

`a`	`not a`
T	F
F	T

`a`	`b`	`a and b`	`a or b`
T	T	T	T
T	F	F	T
F	T	F	T
F	F	F	F

So a and b holds exactly when both do, a or b when at least one does, and not a reverses the value. All three are reserved words: they are part of the syntax and cannot be reassigned or used as names.

Both and and or stop as soon as the answer is settled: in a and b the expression b is never evaluated when a is False, and in a or b it is never evaluated when a is True.

(3 != 2) and (5 % 3 == 0)   # False, since 5 % 3 is 2

The Operators in One Place

Category	Operators
Arithmetic	`+`, `-`, ``, `/`, `//`, `*`, `%`, unary `-`, unary `+`
Relational	`<`, `<=`, `>`, `>=`, `==`, `!=`
Assignment	`=`, `+=`, `-=`, `=`, `/=`, `//=`, `*=`, `%=`, `<<=`, `>>=`
Logical	`and`, `or`, `not`

The compound assignments abbreviate an update in place: total += x means total = total + x.

The bitwise operators (<<, >>, &, |, ^, ~, &=, |=, ^=), and with them <<= and >>=, are not used in this lesson.

Variables and State

An equation such as $y = x^2$ ties $y$ to $x$ permanently: change $x$ and $y$ changes with it. Assignment does not. It creates a binding, at one moment in time, between a name and one object in memory, and the binding stands until it is replaced.

pi = 3.14159
radius = 11.0
area = pi * (radius ** 2)
radius = 14.0

The third statement evaluates pi * (radius ** 2) to the single float 380.13239 and binds area to it. The fourth rebinds radius, and area is untouched: it is bound to a number, not to a formula. This lets Heron’s method overwrite its guess $g$ at every step while the input $x$ stays fixed.

Names and Comments

A program has to be checked by a reader, and a correct program with opaque names is hard to check. The # symbol begins a comment, which the interpreter ignores.

a = 3.14159
b = 11.2
c = a * (b ** 2)

pi = 3.14159
diameter = 11.2
area = pi * ((diameter / 2.0) ** 2)

The two blocks compute different numbers, and only the second makes it visible which one is the area of a circle: the first squares a diameter where it should square a radius, and its names hide the fact.

Multiple Assignment

Several names may be bound at once. Every expression on the right of the = is evaluated in full before any name on the left is rebound, so the two sides do not interfere.

x, y = 2, 3
x, y = y, x

print("x is", x)   # x is 3
print("y is", y)   # y is 2

Exchanging two values therefore needs no third name to hold one of them.

Problem 3.5.

Start from a, b = 1, 1 and perform a, b = b, a + b three times. Give the values of a and b after each of the three steps, and name the sequence they run through. Then say what a, b = b, a + b would produce if the right-hand side were evaluated one name at a time, left to right.

Numbers in Other Bases

The string $2812$ is a representation of a number rather than the number itself. Each digit occupies a position whose value is a power of ten:

2812 = 2 \cdot 10^3 + 8 \cdot 10^2 + 1 \cdot 10^1 + 2 \cdot 10^0 .

The rightmost digit sits in the units place, $10^0 = 1$ , and each position to its left is worth ten times the one before, so the leftmost $2$ of $2812$ stands for two thousand while the rightmost stands for two. This is a positional numeral system: what a digit means depends on where it sits.

Base ten comes from counting on fingers, not from mathematics. Ten is divisible by only four numbers, $1, 2, 5$ and $10$ , which limits how easily fractions can be handled; twelve, divisible by $1, 2, 3, 4, 6$ and $12$ , would serve better. A digital circuit holds two voltage levels, high and low, so machines work in base two, where arithmetic is carried out directly by sequences of logic gates.

That every natural number has exactly one representation of this shape in any base $b > 1$ is Theorem 2.21 of the last lesson, and the notation is fixed by its corollary. Read as a statement about digit strings, it says that the base- $b$ expansion of $n \in \mathbb{N}_0$ is the string $d_r d_{r-1} \cdots d_0$ satisfying three conditions:

$n = d_r b^r + d_{r-1}b^{r-1} + \cdots + d_0 b^0$ ;
every digit satisfies $0 \leqslant d_i < b$ ;
if $n > 0$ then the leading digit $d_r$ is not $0$ , and the expansion of $0$ is the string $0$ in every base.

The first condition says that the digits record how many copies of each power of $b$ are wanted; in decimal the places from the right are units, tens, hundreds, and in binary they are $1, 2, 4, 8, 16, \ldots$ . The second restricts the available digits to $0, 1, \ldots, b-1$ , and without it uniqueness fails: if $\text{X}$ were a decimal digit standing for ten, then $\text{X}2$ and $102$ would both represent one hundred and two. The third bans leading zeros, without which $01423$ and $1423$ would be different strings for one number.

Following the corollary we write

(d_r d_{r-1} \cdots d_0)_b = d_r b^r + d_{r-1} b^{r-1} + \cdots + d_0 b^0

for the number with this expansion, and a string carrying no subscript is decimal.

Remark (Names of the small bases).

The base- $2$ , $3$ , $8$ , $10$ and $16$ expansions are called binary, ternary, octal, decimal and hexadecimal. Bases past ten need more than the ten digits, and the convention is to carry on with letters: $\text{A} = 10$ , $\text{B} = 11$ , and so on up to $\text{Z} = 35$ .

Example 3.6 (One number in six bases).

The decimal expansion of $1023$ is $1023$ itself. Since $1023 = 2^{10} - 1$ , every power of two from $2^0$ to $2^9$ occurs exactly once and the binary expansion is ten ones. For base thirty-six, $1023 = 28 \cdot 36 + 15$ , and $28$ is $\text{S}$ while $15$ is $\text{F}$ . Altogether

1023 = (1111111111)_2 = (1101220)_3 = (1777)_8 = (1023)_{10} = (3\text{FF})_{16} = (\text{SF})_{36} .

Python writes the three bases a machine uses with bin, oct and hex, each returning a string carrying a prefix that names the base:

n = 1023

bin(n)   # '0b1111111111'
oct(n)   # '0o1777'
hex(n)   # '0x3ff'

The same prefixes may be typed directly as literals, so the conversions can be checked against each other:

a = 0b1111111111
b = 0o1777
c = 0x3FF

a == b == c == 1023   # True

For any other base, int takes the base as a second argument and reads a string written in it:

int('1101220', 3)   # 1023
int('sf', 36)       # 1023

Problem 3.6.

Find the binary, ternary, octal, hexadecimal and base- $36$ expansions of $1729$ by hand, using $\text{A}$ to $\text{F}$ as the extra hexadecimal digits and $\text{A}$ to $\text{Z}$ for base thirty-six. Check each against int, and against bin, oct and hex.

Problem 3.7.

A number has octal expansion $(2745)_8$ . Give its decimal value and its hexadecimal expansion.

Problem 3.8.

Let $b > 1$ . Write down, in terms of $b$ , the smallest and the largest number whose base- $b$ expansion has exactly three digits.

Branching

Everything written so far is a straight-line program: the statements run in the order they appear, each exactly once. Such a program is easy to reason about, and limited. If one atomic operation takes one unit of time, a straight-line program of $N$ lines takes at most $N$ units however large its input, because no line ever runs twice.

The first way to let a program do more is branching: a test is evaluated, and the block of statements that runs next depends on the answer.

Conditional Statements

The basic branching construct is if–else. It consists of a test evaluating to True or False, a block run when the test is True, and an optional else block run when it is False.

Python marks the extent of a block by indentation. Where other languages use braces or an end keyword, Python uses the whitespace itself, so the layout of a program shows its structure.

x = 14

if x % 2 == 0:
    print("The integer is even.")
else:
    print("The integer is odd.")

print("Branching complete.")

The test uses x % 2, the remainder on division by two, which is the last digit of the binary expansion of x. It is 0 for even x and 1 for odd. The final print is not indented, so it belongs to neither block and runs either way; indenting it by four spaces would make it part of the else and suppress it for even x.

Because indentation carries meaning, a long expression cannot be broken across lines anywhere. A backslash at the end of a line continues it explicitly, and a line inside unclosed brackets continues implicitly.

# explicit continuation
alpha = 1.61803398875 + \
        2.71828182845 + \
        3.14159265359

# implicit continuation, inside parentheses
beta = (1.61803398875 +
        2.71828182845 +
        3.14159265359)

Nested Conditionals

A block inside a branch may itself branch, which builds a decision tree.

Where the cases are mutually exclusive, a chain of else blocks each containing one if grows an extra level of indentation per case. The keyword elif collapses the chain: its test is evaluated exactly when every test above it has come out False.

n = 15

if n % 2 == 0:
    if n % 3 == 0:
        print("n is a multiple of 6.")
    else:
        print("n is even, but not divisible by 3.")
elif n % 3 == 0:
    print("n is odd and divisible by 3.")
else:
    print("n is not divisible by 2 or 3.")

Compound Tests and Updating State

Tests may be combined with and, or and not. How they are combined changes how much work the program does.

Take the problem of returning the largest positive number among $a$ , $b$ and $c$ , or, if none of them is positive, the smallest of the three. Each of the three is positive or not, so there are $2^3 = 8$ cases, and a program with one branch per case tests the same three comparisons over and over.

Binding a provisional answer and updating it only when a later value beats it replaces the eight cases by three independent tests:

a, b, c = -5, 12, 7

# if none is positive the answer is the smallest, so start there
target = min(a, b, c)

if a > 0:
    target = a
if b > 0 and b > target:
    target = b
if c > 0 and c > target:
    target = c

print(target)   # 12

The built-in min returns the smallest of its arguments, and max the largest. Each of the three variables has its sign examined once.

Conditional Expressions

For a choice between two values rather than between two blocks of work, Python supplies the conditional expression, which packs an if–else into a single expression:

expression_if_true if test else expression_if_false

A variable may therefore be bound according to a test without a multi-line block. The absolute value of Definition 1.65 is given by cases, so there are several ways to compute it. The most direct is a standard if block:

x = -10

if x < 0:
    x = -x

For a body consisting of a single short statement, Python permits writing the block on the same line as the if:

if x < 0: x = -x   # only for very short statements

Branching can also be avoided entirely by using the fact that True and False behave as $1$ and $0$ in arithmetic:

y = (x < 0) * (-x) + (x >= 0) * x   # works, but hard to read

This works, but it is hard to read, it evaluates both branches every time, and it hides the case split inside a multiplication. The conditional expression is clearer:

y = x if x >= 0 else -x

Python also provides the built-in abs for this purpose, so abs(-10) returns 10.

Problem 3.9.

Using conditional expressions and no if statements, write single-line definitions of

the sign of $x$ , which is $-1$ , $0$ or $1$ according as $x$ is negative, zero or positive;
the larger of $x$ and $y$ , without using max;
the distance $|x - y|$ between two reals, without using abs.

Constant Time

Branching does not remove the limit on straight-line programs. Each block is entered at most once on a run, so if one atomic operation takes one unit of time, a branching program of $N$ lines can never exceed $N$ units, and its maximum running time is hard-bounded by a constant $k \leqslant N$ .

Definition 3.7 (Constant time).

An algorithm runs in constant time if there is a constant $k$ , depending on the algorithm alone, such that the algorithm performs at most $k$ atomic operations on every input, whatever the size or magnitude of that input.

Every straight-line program runs in constant time, and so does every branching program, with $k$ the number of lines.

Remark (Beyond constant time).

Constant time is a strong restriction. Consider computing the factorial of an integer $n$ . It requires $n - 1$ multiplications, and $n$ is not bounded, so no fixed number of multiplication statements serves for every $n$ ; a program with one hard-coded branch per value of $n$ would need infinitely many branches and would violate the finiteness in the definition of an algorithm. The same holds for reading the base- $b$ digits of a number, whose count grows like $\log_b n$ . Computations whose length grows with the input need control flow that can return to an earlier instruction.

Problem 3.10.

Let a, b and c be the coefficients of $ax^2 + bx + c$ . Write a program that computes the discriminant $\Delta = b^2 - 4ac$ and reports whether the polynomial has two distinct real roots, one repeated real root, or none. Treat $a = 0$ separately, where the expression is linear rather than quadratic, and say what your program should report when $a = b = 0$ .

Problem 3.11.

Consider the rule which replaces an integer $n$ by $3n + 1$ when $n$ is odd and by $n/2$ when $n$ is even. Using conditional expressions, write a program that applies the rule three times in succession to a given positive integer. Check that starting from $n = 7$ it produces $34$ , and find a starting value below $10$ from which three applications return the starting value itself.

Iteration

Branching programs are bound by constant time: each instruction is executed at most once, so the whole computation is capped by the static length of the source. The base expansions of the first chapter show the limit. Every step applied the same pair of operations, // and %, to the current quotient, and with no way of repeating those operations automatically we performed each step by hand. Computing the factorial of $n$ , testing whether a number is prime, extracting the digits of an arbitrarily large base expansion: these tasks take longer on larger inputs, and no branching program can perform them.

Iteration sends execution back to an instruction already passed.

Definition 3.8 (Iteration).

An iteration, or loop, is a control structure that sends execution back to an instruction it has already passed, so that a block of statements runs repeatedly. How many times it runs is decided by the state of the computation while it runs, not by the length of the program.

Figure 3.2. The shape of a loop. The test is evaluated, the body runs when it holds, and control returns to the test; the loop is left by the other exit.

The While Loop

Python’s while statement has the syntax of if: a test, a colon, and an indented body. The test is evaluated; if it is True the body runs in full and control returns to the test; if it is False the body is skipped and execution continues after the loop.

The following program computes $x^2$ by adding $x$ to a running total $x$ times.

x = 3
ans = 0
num_iterations = 0

while num_iterations != x:
    ans = ans + x
    num_iterations = num_iterations + 1

print(f"{x} squared is {ans}")

Recording the values of the variables each time the test is reached, as though one were the interpreter, is called hand simulation, and it is how we check what a loop does.

Test evaluation	`x`	`ans`	`num_iterations`	Test
1st	3	0	0	`True`
2nd	3	3	1	`True`
3rd	3	6	2	`True`
4th	3	9	3	`False`

On the fourth evaluation num_iterations has reached x, and the program prints 3 squared is 9.

Whether it stops at all depends on x, and there are three cases. If $x = 0$ , the test fails at once, the body never runs, and 0 squared is 0 is printed. If $x > 0$ , the counter starts below x and rises by exactly one per pass, so after $x$ passes it equals x and the loop ends with the right answer. If $x < 0$ , the counter runs through $0, 1, 2, \ldots$ and never equals a negative number: the test is never False, and the program runs forever. This is an infinite loop.

Weakening the test to num_iterations < abs(x) stops the loop after abs(x) passes, but each pass still adds the negative number x, so the program would announce that $(-3)^2 = -9$ . The body has to be corrected too:

x = -3
ans = 0
num_iterations = 0

while num_iterations < abs(x):
    ans = ans + abs(x)
    num_iterations = num_iterations + 1

print(f"{x} squared is {ans}")   # -3 squared is 9

Example 3.9 (The leading digit).

Floor division by ten discards the last decimal digit, so applying it until one digit is left leaves the first digit. How many times it must be applied is not known before the loop starts, which is what a while loop is for.

n = 72658489290098
n = abs(n)

while n >= 10:
    n = n // 10

print(n)   # 7

Two further pieces of Python are needed for the problems below. Writing + between two strings joins them end to end, so 'X' + 'X' is 'XX'. And input(prompt) prints its prompt, waits for the user to type a line, and returns what was typed as a string; int converts a string of digits to the integer it denotes, so int(input('n? ')) reads a number.

Problem 3.12.

The program below should print the letter X a given number of times. Replace the comment by a while loop that appends 'X' to to_print exactly num_x times, and say what your loop does when the user enters $0$ or a negative number.

num_x = int(input('How many times should I print the letter X? '))
to_print = ''
# append X to to_print num_x times
print(to_print)

Leaving a Loop Early

A break statement ends the loop containing it at once and passes control to the first statement after it, without returning to the test.

# the smallest positive integer divisible by both 11 and 12
x = 1

while True:
    if x % 11 == 0 and x % 12 == 0:
        break
    x = x + 1

print(x, 'is divisible by 11 and 12')   # 132 is divisible by 11 and 12

The test while True never fails, so the break is the only way out, and the proof that the loop stops is about the break. This arrangement suits a loop whose exit condition is natural to check partway through the body rather than at the top.

Where one loop sits inside another, a break ends only the loop that immediately contains it; the outer loop carries on.

Problem 3.13.

Write a program that reads ten integers, one at a time, and then prints the largest odd number among them, or a message saying that none was odd. Do not use max.

The For Loop

The loops above share a pattern: a counter is set up, tested at the top, and advanced at the bottom of the body. The for statement does that bookkeeping itself. Its form is

for variable in sequence:
    body

The variable is bound to the first entry of the sequence and the body runs; then to the second, and the body runs again; and so on until the sequence is exhausted or a break intervenes.

total = 0

for num in (77, 11, 3):
    total = total + num

print(total)   # 91

The object (77, 11, 3) is a tuple, an ordered finite sequence written in parentheses.

The Range Function

The sequence is most often produced by range, which generates a progression of integers and takes one, two or three arguments.

With one argument, range(stop) gives $0, 1, \ldots, \text{stop} - 1$ .

for i in range(4):
    print(i)     # 0, then 1, then 2, then 3

With two, range(start, stop) gives $\text{start}, \text{start}+1, \ldots, \text{stop}-1$ . The lower end is included and the upper end is not.

total = 0

for x in range(5, 11):
    total = total + x

print(total == 5 + 6 + 7 + 8 + 9 + 10)   # True

With three, range(start, stop, step) gives $\text{start}, \text{start} + \text{step}, \text{start} + 2\,\text{step}, \ldots$ , and stops before reaching stop. For positive step the last entry is the largest $\text{start} + i\,\text{step}$ below stop; a negative step descends instead, so range(40, 5, -10) gives $40, 30, 20, 10$ .

total = 0

for x in range(10, 3, -1):
    if x % 2 == 1:
        total = total + x

print(total)   # 9 + 7 + 5 = 21

Choosing the step to land on the right numbers is often more trouble than testing them inside the body. The following sums the odd numbers between m and n whatever the parity of m:

m, n = 4, 10
total = 0

for x in range(m, n + 1):
    if x % 2 == 1:
        total = total + x

print(total)   # 5 + 7 + 9 = 21

The two-argument form covers the one-argument form: range(0, 3) produces the same sequence as range(3). The entries are produced one at a time as the loop asks for them rather than stored all at once, so range(1000000) costs no more memory than range(3).

Remark (Which loop to use).

A for loop is the right choice when the number of passes is settled before the loop begins, since range then states that number and no counter can be mismanaged. A while loop is the right choice when it is not: the leading-digit program above stops when the number falls below ten, and how many divisions that takes is a fact about the input rather than about the program.

Example 3.10 (Squaring by repeated addition again).

The squaring program loses its counter entirely when written with for:

x = -3
ans = 0

for num_iterations in range(abs(x)):
    ans = ans + abs(x)

print(f"{x} squared is {ans}")   # -3 squared is 9

There is no explicit test and no explicit increment; range supplies both.

Reassigning the Loop Variable

Assigning to the loop variable inside the body does not disturb the loop.

for i in range(2):
    print(i)
    i = 0
    print(i)

This prints 0, 0, 1, 0 and stops. The sequence is fixed when the for statement is first reached, and at the start of each pass the variable is rebound to the next entry of it, whatever happened to the variable in between. The loop is equivalent to

index = 0
last_index = 1

while index <= last_index:
    i = index
    print(i)
    i = 0
    print(i)
    index = index + 1

For the same reason, changing a variable that was used in the range call has no effect, because the call is evaluated once:

x = 1

for i in range(x):
    print(i)
    x = 4

# prints 0, and nothing else

An inner for is a different matter: its range call is reached afresh on every pass of the outer loop and so is evaluated again.

x = 3

for j in range(x):
    print('Outer')
    for i in range(x):
        print('  Inner')
        x = 2

The outer range(x) is evaluated once, with $x = 3$ , so the outer loop makes three passes. The inner range(x) sees $x = 3$ on the first pass and $x = 2$ afterwards, giving $3 + 2 + 2 = 7$ inner passes in total.

Iterating Over a String

A string is a sequence of characters. Its positions are numbered from $0$ , so a string of length $k$ occupies positions $0, 1, \ldots, k-1$ : len(s) gives the length, s[i] gives the character at position i, and the slice s[i:j] gives the characters at positions i up to but not including j. That upper end is excluded for the same reason it is excluded from range, and the two conventions agree: s[0:len(s)] is the whole of s, and the positions it covers are exactly those produced by range(len(s)).

Combined with in, the for statement walks a string directly, binding the variable to one character at a time and dispensing with the positions altogether.

total = 0

for c in '12345678':
    total = total + int(c)

print(total)   # 36

Problem 3.14.

Write a program that computes $5 + 6 + \cdots + 100$ with a for loop, and check the result against the closed form for an arithmetic progression obtained in the last lesson. Then do the same for $5 + 7 + 9 + \cdots + 99$ , once by choosing the step of the range and once by testing inside the body.

Nested Loops

A loop inside a loop runs the inner loop to completion on every pass of the outer one.

Example 3.11 (Patterns).

An $n \times n$ block of asterisks needs one loop for the rows and one for the columns:

n = 5

for row in range(n):
    for col in range(n):
        print('*', end='')
    print()

*****
*****
*****
*****
*****

The bare print() after the inner loop ends the line. Letting the inner range depend on the outer variable changes the shape:

n = 5

for row in range(n):
    print(row, end=' ')
    for col in range(row):
        print('*', end=' ')
    print()

0
1 *
2 * *
3 * * *
4 * * * *

Row $k$ carries $k$ asterisks, so the block becomes a triangle.

Continue and Pass

Two keywords sit alongside break. A continue abandons the rest of the current pass and goes straight to the next one: back to the test for a while, on to the next entry for a for. A pass does nothing, and exists because Python’s syntax requires a statement in places where no action is wanted.

for n in range(200):
    if n % 3 == 0:
        continue
    elif n == 8:
        break
    else:
        pass
    print(n, end=' ')

# 1 2 4 5 7

The multiples of three never reach the print, the loop ends when n reaches $8$ , and the remaining values pass through the else branch and are printed.

Divisibility and Primality

Definition 3.12 (Divisibility).

Let $d, n \in \mathbb{Z}$ . We say $d$ divides $n$ , written $d \mid n$ , if $n = dq$ for some $q \in \mathbb{Z}$ ; equivalently, for $d \neq 0$ , if $n \bmod d = 0$ . In Python this is the test n % d == 0.

Definition 3.13 (Prime and composite).

An integer $n \geqslant 2$ is prime if its only positive divisors are $1$ and $n$ , and composite otherwise. The integers $0$ and $1$ and the negative integers are neither.

Checking that $91$ is composite takes a single operation once the divisor $7$ is known, since 91 % 7 == 0 settles it; finding the divisor is where the work lies. Read as an instruction, the definition says to test every candidate between $2$ and $n - 1$ and to stop at the first one that divides.

n = 91
is_prime = n >= 2

for factor in range(2, n):
    if n % factor == 0:
        is_prime = False
        break

if is_prime:
    print(f'{n} is prime')
else:
    print(f'{n} is not prime')

# 91 is not prime

One divisor settles the question, so the loop stops at the first one it finds. Wrapping the whole thing in a second loop lists the primes below a bound:

for n in range(2, 100):
    is_prime = True
    for factor in range(2, n):
        if n % factor == 0:
            is_prime = False
            break
    if is_prime:
        print(n, end=' ')

# 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97

Trial Division to the Square Root

Testing every candidate up to $n - 1$ is more than necessary.

Proposition 3.14 (A composite number has a small divisor).

Let $n \geqslant 2$ . Then $n$ is composite if and only if some integer $d$ with $2 \leqslant d \leqslant \sqrt{n}$ divides $n$ .

Discussion.

Divisors come in pairs: if $d \mid n$ then $d$ and $n/d$ are both divisors and their product is $n$ . A product of two numbers both exceeding $\sqrt{n}$ exceeds $n$ , so the two members of a pair cannot both lie above $\sqrt{n}$ , and one of them is at or below it. The proof takes the least divisor above $1$ ; its partner is then the larger of the two, and the inequality $d \leqslant n/d$ can be squared. The converse direction is immediate: a divisor in that range is neither $1$ nor $n$ , because $\sqrt{n} < n$ once $n \geqslant 2$ .

Proof.

Suppose $n$ is composite. The set $D = \{\, d \in \mathbb{Z} : d \geqslant 2 \text{ and } d \mid n \,\}$ contains $n$ , so it is non-empty; let $d$ be its least element and write $n = dq$ with $q \in \mathbb{Z}$ , so that $q \geqslant 1$ and $q \mid n$ .

We first rule out $q = 1$ . If $q = 1$ then $d = n$ . But $n$ is composite, so it has a divisor $e$ with $1 < e < n$ ; that $e$ lies in $D$ and is smaller than $n = d$ , contradicting the minimality of $d$ . Hence $q \geqslant 2$ , so $q \in D$ and therefore $q \geqslant d$ . Consequently

d^2 \leqslant dq = n ,

so $d \leqslant \sqrt{n}$ .

Conversely, suppose $2 \leqslant d \leqslant \sqrt{n}$ and $d \mid n$ . From $n \geqslant 2$ we get $\sqrt{n} < n$ , so $d \neq n$ , and $d \neq 1$ by hypothesis. Thus $n$ has a positive divisor other than $1$ and $n$ , so it is composite.

Only the integers up to $\sqrt{n}$ need be tested, and $2$ can be dealt with separately so that the loop skips the even candidates:

n = 1010809
is_prime = n >= 2

if n > 2 and n % 2 == 0:
    is_prime = False
else:
    max_factor = round(n ** 0.5)
    for factor in range(3, max_factor + 1, 2):
        if n % factor == 0:
            is_prime = False
            break

print(f'{n} is prime: {is_prime}')   # 1010809 is prime: True

round(n ** 0.5) returns either $\lfloor \sqrt{n} \rfloor$ or one more, never less, so the loop may test one candidate too many and never one too few.

The first program tests up to $n - 2$ candidates and the second about $\sqrt{n}/2$ : for $n = 1010809$ , about a million tests against about five hundred. Python’s time module measures it. The statement import time makes the module’s tools available, and time.time() returns the current time in seconds. A colon inside the braces of an f-string says how to format the value: :.2f prints it with two digits after the decimal point.

import time

n = 1010809

time0 = time.time()
is_prime_basic = True
for factor in range(2, n):
    if n % factor == 0:
        is_prime_basic = False
        break
time1 = time.time()
print(f'Basic: {(time1 - time0) * 1000:.2f} ms')

time0 = time.time()
is_prime_fast = n >= 2
if n > 2 and n % 2 == 0:
    is_prime_fast = False
else:
    max_factor = round(n ** 0.5)
    for factor in range(3, max_factor + 1, 2):
        if n % factor == 0:
            is_prime_fast = False
            break
time1 = time.time()
print(f'Optimised: {(time1 - time0) * 1000:.2f} ms')

print(is_prime_basic == is_prime_fast)   # True

The two agree, and on an ordinary machine the first takes tens of milliseconds where the second takes a small fraction of one.

Searching for the $n$ th Object

Finding the $n$ th number with a given property is a different kind of problem: the answer is not known in advance, so there is no range to run over. A counter of successes and a candidate that advances by one at a time turn it into a while loop.

target = 5
found = 0
guess = 0

while found <= target:
    guess = guess + 1
    if guess % 4 == 0 or guess % 7 == 0:
        found = found + 1

print(f'Counting from zero, entry {target} of the multiples of 4 or 7 is {guess}')
# entry 5 is 16

The multiples of four or seven begin $4, 7, 8, 12, 14, 16$ , and counting from zero the entry numbered $5$ is $16$ . Substituting the primality test for the divisibility test finds the $n$ th prime:

target = 10
found = 0
guess = 1

while found <= target:
    guess = guess + 1
    is_prime = guess >= 2
    if guess > 2 and guess % 2 == 0:
        is_prime = False
    else:
        max_factor = round(guess ** 0.5)
        for factor in range(3, max_factor + 1, 2):
            if guess % factor == 0:
                is_prime = False
                break
    if is_prime:
        found = found + 1

print(f'Counting from zero, prime {target} is {guess}')   # prime 10 is 31

The primes are $2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31$ , and counting from zero the one numbered $10$ is $31$ .

Problem 3.15.

Write a program that prints the sum of the primes strictly between $2$ and $1000$ , using a primality test nested inside a loop over the odd integers from $3$ to $999$ . Then say how many candidate divisors your program tests in total, and how many the version without the square-root bound would test.

Digits in an Arbitrary Base

In the first chapter we read off base- $b$ expansions by hand, dividing by $b$ , recording the remainder as the next digit from the right, and continuing with the quotient until it reached zero. Automating that needs a way of repeating instructions until a condition is met, which the while loop provides. The number of repetitions is the number of digits, and it is not known before the divisions are done.

Proposition 3.15 (Digit extraction).

Let $b > 1$ and $n \in \mathbb{N}$ . Define $n_0 = n$ and $n_{k+1} = \lfloor n_k / b \rfloor$ . Then $n_k = 0$ for some $k$ , the least such $k$ is $m = \lfloor \log_b n \rfloor + 1$ , and for $0 \leqslant i < m$

n_i \bmod b = z_i ,

where $z_{m-1} \cdots z_1 z_0$ is the base- $b$ expansion of $n$ .

Discussion.

One pass of the loop performs the split $z = b\lfloor z/b \rfloor + (z \bmod b)$ , which removes the last digit. The proof identifies $n_k$ explicitly, as the number whose digits are the top $m - k$ digits of $n$ , and proves this by induction on $k$ . The step is the split applied to $n_k$ , and the remainder is the digit $z_k$ by the uniqueness of quotient and remainder, as in the uniqueness half of Theorem 2.21. The number of steps then follows: the sum defining $n_k$ is empty exactly when $k = m$ , and is at least $1$ before that, because its leading digit is not zero.

Proof.

By Corollary 2.22 the number $n$ has a unique expansion

n = \sum_{i=0}^{m-1} z_i b^i, \qquad z_i \in \{0, \ldots, b-1\}, \quad z_{m-1} \neq 0, \quad m = \lfloor \log_b n \rfloor + 1 .

We claim that

n_k = \sum_{i=k}^{m-1} z_i b^{\,i-k} \qquad (0 \leqslant k \leqslant m).

For $k = 0$ this is the expansion itself. Assume it for some $k < m$ and split off the term $i = k$ :

n_k = z_k + b\sum_{i=k+1}^{m-1} z_i b^{\,i-k-1} .

The sum on the right is an integer and $0 \leqslant z_k < b$ , so this is the division of $n_k$ by $b$ with quotient and remainder, and by the uniqueness of that division

n_{k+1} = \left\lfloor \frac{n_k}{b} \right\rfloor = \sum_{i=k+1}^{m-1} z_i b^{\,i-k-1}, \qquad n_k \bmod b = z_k ,

which is the claim at $k+1$ together with the stated identity for the digits.

At $k = m$ the sum is empty, so $n_m = 0$ . For $k < m$ every term is non-negative and the term $i = m-1$ is $z_{m-1}b^{\,m-1-k} \geqslant 1$ , so $n_k \geqslant 1$ . Hence $m$ is the least index at which the sequence vanishes.

The loop below carries out the proposition. Digits are produced from the last to the first, so each new one is put in front of what has been built so far, and digits above nine are turned into letters: str(d) turns the number d into the string of its decimal digits, ord(c) gives the code number of the character c, chr(k) gives the character with code k, and the codes of A to Z run consecutively.

n = 12345
b = 17
digits = ''

while n > 0:
    remainder = n % b
    if remainder < 10:
        digits = str(remainder) + digits
    else:
        digits = chr(ord('A') + remainder - 10) + digits
    n = n // b

print(digits)   # 28C3

Example 3.16 (Checking the expansion).

Reading $(28\text{C}3)_{17}$ back gives

2 \cdot 17^3 + 8 \cdot 17^2 + 12 \cdot 17 + 3 = 9826 + 2312 + 204 + 3 = 12345 ,

as the proposition says.

Problem 3.16.

The loop above prints nothing when $n = 0$ . Say why, in terms of the hypotheses of the proposition, and repair it so that it prints '0'. Then use it to find the base- $7$ and hexadecimal expansions of $9999$ , and check them against the by-hand method of the first chapter.

Problem 3.17.

Write a program that repeatedly asks the user for a string and prints it back, stopping when the user enters 'done'. It should then print 'Bye!' followed by the number of strings entered, not counting 'done'.

Running Time

Timing the two primality tests measured one machine at one time. The number of instructions a program performs depends on the compiler and on the hardware, and we do not in any case know it exactly. We want a statement about the algorithm instead: how the amount of work grows with the input.

Definition 3.17 (Elementary operation and running time).

An elementary operation is one the machine performs in a bounded number of clock cycles independently of the values involved: an arithmetic operation or a comparison on numbers of bounded size, a read or a write of one stored value. Both a // b and a % b are elementary in this sense.

The running time of an algorithm is the number of elementary operations it performs, counted as a function of its input.

Two things remain to be fixed: how the size of an input is measured, and how precisely we count.

Landau Notation

Definition 3.18 (Landau's $O$ ).

Let $g : \mathbb{N} \to \mathbb{R}_{\geqslant 0}$ . Then $O(g)$ is the set of functions $f : \mathbb{N} \to \mathbb{R}_{\geqslant 0}$ for which there exist $\alpha \in \mathbb{R}_{>0}$ and $n_0 \in \mathbb{N}$ with

f(n) \leqslant \alpha \cdot g(n) \qquad \text{for all } n \geqslant n_0 .

The constant $\alpha$ must not depend on $n$ ; were it allowed to, every function would lie in $O(1)$ and the definition would say nothing. Nor does the inequality have to hold everywhere: it may fail for finitely many $n$ , so changing $f$ at the first million values leaves the statement untouched.

Instead of $f \in O(g)$ one usually writes

f = O(g), \qquad\text{or}\qquad f(x) = O\bigl(g(x)\bigr) \text{ as } x \to \infty ,

read ” $f$ is big-Oh of $g$ ”. The equals sign here is not the symmetric one, since $O(g)$ is a set and $f$ is a member of it; the notation is standard nonetheless.

Example 3.19 (A cubic is $O(x^4)$ ).

Take $f(x) = 4x^3 + 7x$ and $g(x) = x^4$ . For $x \geqslant 1$ we have $x^3 \leqslant x^4$ and $x \leqslant x^4$ , so

4x^3 + 7x \leqslant 4x^4 + 7x^4 = 11x^4 ,

and $\alpha = 11$ with $n_0 = 1$ meets the definition. Hence $4x^3 + 7x = O(x^4)$ .

Example 3.20 (A tight bound).

Take $f(n) = 3n^2 + 5n + 7$ and $g(n) = n^2$ . For $n \geqslant 1$ we have $n \leqslant n^2$ and $1 \leqslant n^2$ , so

3n^2 + 5n + 7 \leqslant 3n^2 + 5n^2 + 7n^2 = 15n^2 ,

and $\alpha = 15$ with $n_0 = 1$ serves. Hence $3n^2 + 5n + 7 = O(n^2)$ .

Here the bound grows at the same rate as $f$ itself, where the previous example bounded a cubic by a quartic. Both statements are true, but the cubic-by-quartic one loses information, since $x^4$ grows strictly faster than $4x^3 + 7x$ ; the same argument with $\alpha = 11$ gives the sharper $4x^3 + 7x = O(x^3)$ . A function lies in $O(g)$ for many different $g$ , and the useful statement uses the slowest-growing $g$ available.

Example 3.21 (When the definition fails).

Not every pair of functions is related this way: $n^2$ is not $O(n)$ . Suppose it were, so that $n^2 \leqslant \alpha n$ for some $\alpha > 0$ and all $n \geqslant n_0$ . Dividing by $n$ , which is positive, gives $n \leqslant \alpha$ for all $n \geqslant n_0$ . But

n = \max\bigl(n_0, \lceil \alpha \rceil\bigr) + 1

satisfies $n \geqslant n_0$ and $n > \alpha$ , which contradicts it. So no constant serves, and the direction of an $O$ statement is not reversible: $n = O(n^2)$ holds while $n^2 = O(n)$ does not.

The argument of the first two examples works for any polynomial.

Proposition 3.22 (Polynomials).

Let $f(n) = a_d n^d + a_{d-1}n^{d-1} + \cdots + a_1 n + a_0$ with every $a_i \geqslant 0$ and $d \in \mathbb{N}_0$ . Then $f = O(n^d)$ .

Discussion.

The proof uses one inequality: for $n \geqslant 1$ and $i \leqslant d$ we have $n^i \leqslant n^d$ , because raising a number at least $1$ to a larger exponent cannot decrease it. Applying it to each term replaces every power by the top power, and what is left is the sum of the coefficients, which serves as the constant $\alpha = a_d + \cdots + a_0$ of the definition. Non-negative coefficients let each term be bounded separately; with negative coefficients the same bound holds after taking absolute values of the coefficients.

Proof.

Let $n \geqslant 1$ . For each $i$ with $0 \leqslant i \leqslant d$ we have $n^i \leqslant n^d$ , so $a_i n^i \leqslant a_i n^d$ since $a_i \geqslant 0$ . Adding these $d+1$ inequalities,

f(n) = \sum_{i=0}^{d} a_i n^i \;\leqslant\; \left(\sum_{i=0}^{d} a_i\right) n^d .

Taking $\alpha = \sum_{i=0}^{d} a_i$ , which is a positive constant unless every $a_i$ is $0$ , and $n_0 = 1$ , the definition is satisfied.

Remark (The limit form).

For a reader who has met limits there is a shorter route to most $O$ statements. Suppose $g(n) \neq 0$ from some point on and the ratio $f(n)/g(n)$ tends to a finite limit,

\lim_{n \to \infty} \frac{f(n)}{g(n)} = L < \infty .

Then $f = O(g)$ : beyond some $n_0$ the ratio stays below $L + 1$ , so $\alpha = L + 1$ meets the definition. The cubic example is settled in one line this way, since $(4x^3 + 7x)/x^4 \to 0$ , and so is the tight bound, since $(3n^2 + 5n + 7)/n^2 \to 3$ .

The converse fails only because the ratio need not converge at all, and replacing the limit by the limit superior repairs it: $f = O(g)$ holds exactly when

\limsup_{n \to \infty} \frac{f(n)}{g(n)} < \infty .

A limit of $0$ says more than $O$ does. It says that $f$ is negligible against $g$ rather than merely bounded by a multiple of it, and that stronger relation is written $f = o(g)$ ; so $4x^3 + 7x = o(x^4)$ , while $3n^2 + 5n + 7 = O(n^2)$ is not $o(n^2)$ .

Remark (What $O$ does and does not see).

The notation is insensitive to scaling: if $f = O(g)$ then $Cf = O(Dg)$ for any non-zero constants $C$ and $D$ . It is equally insensitive to any finite initial stretch of the two functions. What it describes is therefore the asymptotic behaviour of $f$ and $g$ , their behaviour for large inputs rather than at any one input. Constant factors depend on the machine and the compiler, which we do not model, so this is the level of precision we want; for the same reason an $O$ bound alone does not decide which of two programs to run on a given machine.

The Cost of Schoolbook Arithmetic

We all learned at school how to add and multiply natural numbers written in decimal: once $m + n$ and $mn$ are known for the single digits $0 \leqslant m, n \leqslant 9$ , sums and products of arbitrary numbers follow by working column by column and carrying. These schoolbook methods are algorithms in the sense of the first chapter, and we can count their cost.

Remark (The base does not matter).

There is nothing special about ten here. The same algorithms work, with minor changes, in any base, binary included. Binary is convenient for multiplication, because the table of single-digit products that has to be known in advance is very much smaller.

Throughout this section the size of the input is the number of digits, which for $x$ written in base $b$ is $\lfloor \log_b x \rfloor + 1$ by Corollary 2.22.

Proposition 3.23 (Cost of schoolbook addition).

Fix a base $b \geqslant 2$ . Computing $x + y$ by the schoolbook algorithm takes $O(n)$ elementary operations, where $n$ is the larger of the numbers of base- $b$ digits of $x$ and of $y$ .

Discussion.

The algorithm treats one column at a time, and each column costs at most a fixed amount, however large the numbers are. A single column adds three quantities: the digit of $x$ there, the digit of $y$ there, and the carry coming in from the column to its right. The first two lie in $\{0, \ldots, b-1\}$ and the third is $0$ or $1$ , so there are at most $2b^2$ possible columns to deal with, a number fixed once $b$ is fixed and independent of $n$ . So each column costs at most some constant $C = C(b)$ , there are $n$ columns and at most one extra step to write a final carry, and the count is $Cn + C$ . Padding the shorter number with leading zeros makes both numbers $n$ digits long.

Proof.

Write $x$ and $y$ in base $b$ , padding the shorter expansion with leading zeros so that both have $n$ digits.

The algorithm works through the columns from right to left. At each column it adds three quantities: the digit of $x$ in that column, the digit of $y$ in that column, and the carry from the preceding column. The two digits lie in $\{0, \ldots, b-1\}$ and the carry is $0$ or $1$ , so there are finitely many possible single-column computations, their number depending on $b$ alone. Since $b$ is fixed, there is a constant $C$ such that every single-column computation takes at most $C$ elementary operations.

The algorithm performs one such computation for each of the $n$ columns and at most one further step to write a final carry, so its running time is at most $Cn + C$ . By the proposition on polynomials this is $O(n)$ .

No algorithm does better than $O(n)$ here, since the output has about $n$ digits and writing it down takes that long. Schoolbook multiplication costs more.

Proposition 3.24 (Cost of schoolbook multiplication).

Fix a base $b \geqslant 2$ . Computing $xy$ by the schoolbook algorithm takes $O(n^2)$ elementary operations, with $n$ as above.

Discussion.

The algorithm has two stages, bounded separately. In the first it forms one partial product for each digit of $y$ : multiplying the whole of $x$ by a single digit is a column-by-column pass of the kind already costed, so it is $O(n)$ , and there are $n$ digits of $y$ , giving $O(n^2)$ . Shifting a partial product left only decides where its digits are written. In the second stage the $n$ partial products are added, and each addition involves numbers of at most $2n$ digits, so by the previous proposition each costs $O(n)$ and the $n$ of them cost $O(n^2)$ . Two stages of $O(n^2)$ make $O(n^2)$ .

Proof.

Write $x$ and $y$ in base $b$ , padded to $n$ digits each.

The algorithm forms $n$ partial products, one for each digit $y_j$ of $y$ . Forming the one belonging to $y_j$ means multiplying $y_j$ by each of the $n$ digits of $x$ , one column at a time and carrying where needed, and then shifting the result $j$ places to the left to obtain $x \cdot y_j b^{\,j}$ . Each single-digit product with a carry is one of finitely many computations depending on $b$ alone, so each partial product costs $O(n)$ and all $n$ of them cost $O(n^2)$ .

It then adds the $n$ partial products. Each is at most $2n$ digits long, so by the previous proposition each addition costs $O(n)$ , and $n$ of them cost $O(n^2)$ .

Both stages are $O(n^2)$ , so there are constants bounding each by a multiple of $n^2$ beyond some point; adding the two bounds gives a constant bounding the total, and the running time is $O(n^2)$ .

Remark (Faster multiplication).

Multiplication algorithms asymptotically better than the schoolbook one do exist, though they are a great deal more complicated. The first was found by Karatsuba in 1960 and multiplies two $n$ -digit numbers in $O(n^{\alpha})$ operations with $\alpha = \log 3 / \log 2 \approx 1.58$ . More recently Harvey and van der Hoeven gave an $O(n \log n)$ algorithm, which is believed to be the best possible.

This last result also shows a limitation of the notation. The running time is bounded by $Cn\log n$ for some constant $C$ , but $C$ is very large: the algorithm beats its rivals only on enormous inputs, and at the sizes that arise in practice methods with worse asymptotic behaviour and smaller constants are faster.

The Cost of Trial Division

Remark (The cost of the obvious method).

The definition of primality suggests testing, for a given $n \geqslant 2$ , every pair $a, b$ with $2 \leqslant a, b \leqslant n/2$ to see whether $n = ab$ . That is up to $(n/2 - 1)^2$ multiplications. Today’s machines perform several billion operations a second, and even so an eight-digit input on this method would occupy one of them for several hours.

Trial division does much better.

Proposition 3.25 (Cost of trial division).

Deciding whether $n \geqslant 2$ is prime by testing every candidate divisor from $2$ to $\lfloor \sqrt{n} \rfloor$ takes $O(\sqrt{n})$ elementary operations.

Discussion.

Each pass of the loop performs a fixed amount of work, one remainder and one comparison, both elementary, so the running time is a constant multiple of the number of passes. The loop runs over the integers from $2$ to $\lfloor \sqrt n \rfloor$ and may stop early at a divisor, so the count is at most $\lfloor \sqrt n \rfloor - 1$ ; the floor is at most $\sqrt n$ , and the constants are absorbed by the $O$ . That stopping at $\sqrt n$ rather than at $n - 1$ is correct is the proposition on small divisors.

Proof.

By the proposition on small divisors, $n$ is composite exactly when some $d$ with $2 \leqslant d \leqslant \sqrt{n}$ divides it, so the loop over $d = 2, \ldots, \lfloor \sqrt{n} \rfloor$ decides the question. It makes at most $\lfloor \sqrt{n}\rfloor - 1 \leqslant \sqrt{n}$ passes, and each pass computes one remainder and one comparison, which is a bounded number $C$ of elementary operations. The total is at most $C\sqrt{n}$ , which is $O(\sqrt{n})$ .

Remark (Avoiding the square root).

It is not obvious that $\lfloor \sqrt{n} \rfloor$ can itself be computed with an elementary operation, and the algorithm need not compute it. Increasing the candidate $i$ by $1$ and stopping as soon as $i \cdot i > n$ tests exactly the same candidates and uses only multiplication and comparison. Every step of the algorithm is then well defined for every admissible input, the algorithm stops after finitely many steps, and it returns the right answer, so it computes the function $f : \mathbb{N} \to \{\text{yes}, \text{no}\}$ taking the value yes exactly at the primes. We write $\{\text{true}, \text{false}\}$ or $\{0, 1\}$ for the two values as well.

Remark (Fast in $n$, slow in the input).

An $O(\sqrt{n})$ bound looks good, but $n$ is not the size of the input. The instance handed to the algorithm is the digit string of $n$ , whose length is $m = \lfloor \log_b n \rfloor + 1$ , so $n$ is about $b^{m}$ and $\sqrt{n}$ is about $b^{m/2}$ . Measured against the length of its input, trial division takes exponentially many steps, so a three-hundred-digit number is out of its reach at any realistic speed.

Problem 3.18.

Give the running time of each of the following in $O$ notation, as a function of $n$ , and justify each answer.

Summing the integers from $1$ to $n$ with a loop.
Summing the integers from $1$ to $n$ with the closed form.
Printing every pair $(i, j)$ with $1 \leqslant i < j \leqslant n$ .
Extracting the base- $b$ digits of $n$ by repeated division.

Problem 3.19.

A product $xy$ may be computed by adding $x$ to a running total $y$ times, using no multiplication at all. Let $x$ and $y$ have $n$ digits in base $b$ .

Give the running time of this method as a function of $n$ and $b$ .
Evaluate that count and the $n^2$ of the schoolbook algorithm at $b = 10$ for $n = 1$ , $n = 3$ and $n = 20$ . On a machine performing $10^9$ operations a second, say for which of the three the repeated-addition method is still usable.
Both methods perform additions of $n$ -digit numbers, and only one of them is out of reach for a twenty-digit input. Say which quantity in your answer to the first part is responsible, and why measuring the input by $n$ rather than by $y$ is what makes the difference visible.

Problem 3.20.

Two programs settle the same problem on inputs of size $n$ . The first performs $100n$ elementary operations, the second $n^2/100$ .

Find every $n$ at which the second is the faster, and the size at which the first overtakes it.
Give the running time of each in $O$ notation, and say what those two statements do and do not tell you about which program to run.
A machine performs $10^9$ operations a second and no input ever exceeds $n = 5000$ . Which program should be run, and how long does it take?

Search and Approximation

The loops of the previous chapters mostly checked something: whether any candidate divides $n$ , whether every character of a string is a digit. The loops of this chapter search for a value: they try candidates until one works.

Exhaustive Enumeration

The simplest search strategy is the one the primality test already used: try every candidate in some collection until one works. When the collection is finite, or can be made finite by bounding the range, this is exhaustive enumeration, and it finds a solution whenever one exists.

Cube Roots

Suppose we want the integer cube root of a perfect cube. Given an integer $n$ , we seek an integer $x$ with $x^3 = n$ , or a report that no such integer exists.

The strategy is direct: test $x = 0, 1, 2, \ldots$ in order until either $x^3 = |n|$ , a success, or $x^3 > |n|$ , a failure, the latter being conclusive because $a < b$ implies $a^3 < b^3$ for non-negative integers. For negative $n$ the cube root is the negative of the cube root of $|n|$ .

n = 27
x = 0

while x ** 3 < abs(n):
    x = x + 1

if x ** 3 != abs(n):
    print(f'{n} is not a perfect cube')
else:
    if n < 0:
        x = -x
    print(f'Cube root of {n} is {x}')

# Cube root of 27 is 3

Hand simulating for $n = 27$ :

Test evaluation	`x`	`x ** 3`	`x ** 3 < 27`
1st	0	0	`True`
2nd	1	1	`True`
3rd	2	8	`True`
4th	3	27	`False`

The loop stops with $x = 3$ , and since $3^3 = 27 = |n|$ the program reports a cube.

Problem 3.21.

Trace the program above for $n = 8$ , $n = -8$ and $n = 9$ . In each case build the hand-simulation table, state the value of x when the loop stops, and say whether the program reports a perfect cube.

Example 3.26 (The speed of exhaustive search).

Take $n = 1{,}957{,}816{,}251$ . Its cube root is $1{,}251$ , so the loop makes $1{,}251$ passes and finishes at once. Take instead $n = 7{,}406{,}961{,}012{,}236{,}344{,}616$ , whose cube root is $1{,}949{,}306$ : the loop makes nearly two million passes and still finishes in well under a second. At billions of instructions a second, a million passes take a fraction of a second.

Termination and Decrementing Functions

Every loop in a correct program must stop, unless it is deliberately endless. To prove that one does, we exhibit a quantity that strictly decreases at every pass and cannot go below zero.

Definition 3.27 (Decrementing function).

A decrementing function for a loop is an integer-valued expression $D$ in the program’s variables such that

$D \geqslant 0$ whenever the loop test holds, and
$D$ strictly decreases at every pass of the body.

A loop admitting a decrementing function stops after at most $D_0$ passes, where $D_0$ is the initial value of $D$ .

With it, “the loop eventually stops” can be proved. For the cube-root search a suitable choice is $D = \lceil |n|^{1/3}\rceil - x$ , written with the ceiling of the last lesson, which may also be had from the floor as $\lceil x\rceil = -\lfloor -x\rfloor$ .

Theorem 3.28 (Termination of the cube-root search).

The exhaustive cube-root search stops for every integer $n$ .

Discussion.

The variable $x$ increases rather than decreases, so it is not itself a decrementing function; what decreases is the distance from $x$ to the value at which the loop stops, and the loop stops once $x^3$ reaches $|n|$ , that is, once $x$ reaches $|n|^{1/3}$ . Since $x$ is an integer this value is rounded up, which is where the ceiling enters. The two conditions of the definition then have to be checked separately: non-negativity comes from the loop test, since the test holding means $x$ has not yet reached the target, and the strict decrease comes from the body, since the body adds exactly $1$ to $x$ and does not change the target.

Proof.

Put $D = \lceil |n|^{1/3} \rceil - x$ . Initially $x = 0$ , so $D = \lceil |n|^{1/3}\rceil \geqslant 0$ .

Suppose the loop test $x^3 < |n|$ holds. Then $x < |n|^{1/3} \leqslant \lceil |n|^{1/3}\rceil$ , and both sides being integers gives $D \geqslant 1$ , so in particular $D \geqslant 0$ .

Each pass replaces $x$ by $x + 1$ and changes nothing else, so $D$ falls by exactly $1$ . Being a non-negative integer that falls by $1$ each pass, $D$ can do so at most $\lceil |n|^{1/3}\rceil$ times, and the loop stops after at most that many passes.

Note (Decrementing functions as a diagnostic).

When a program appears to run forever, the definition suggests where to look. Identify the quantity that ought to be decreasing; if there is none, the loop has no decrementing function, which suggests that the loop may never end. Otherwise print the candidate at every pass, and if the printed values fail to fall, the fault is in the body. Deleting x = x + 1 from the cube-root search, for instance, leaves $D = \lceil |n|^{1/3}\rceil$ at every pass, constant instead of decreasing.

Remark (The cost of exhaustive enumeration).

Exhaustive enumeration is correct and simple, but it can be slow. The cube-root search tests $\lceil |n|^{1/3}\rceil$ candidates, so its running time is $O(n^{1/3})$ . For $n = 10^{12}$ that is $10^4$ passes, which is quick; for $n = 10^{30}$ it is $10^{10}$ passes, minutes or hours. Bisection search needs about a hundred steps for the same $n$ .

Approximate Solutions

The cube-root search demands an exact integer answer, so it works only on perfect cubes. Many numerical problems have no exact answer in the integers, or even in the rationals: $\sqrt{2}$ is irrational, and no finite program returns it. We ask instead for an approximate answer, within a stated tolerance.

Definition 3.29 ( $\varepsilon$ -approximation).

Let $f$ be a function, $y$ a target value and $\varepsilon > 0$ a prescribed tolerance. An $\varepsilon$ -approximation to a solution of $f(x) = y$ is a value $\hat{x}$ with

|f(\hat{x}) - y| < \varepsilon .

The tolerance is chosen by whoever writes the program. A smaller $\varepsilon$ demands a more accurate answer, and can take much more computation.

Exhaustive Search for Square Roots

Exhaustive enumeration adapts to the approximate setting. Rather than the integers $0, 1, 2, \ldots$ we test the values $0, \delta, 2\delta, 3\delta, \ldots$ for a small step $\delta > 0$ , and accept the first $\hat{x}$ with $|\hat{x}^2 - n| < \varepsilon$ .

n = 25
epsilon = 0.01
step = 0.0001
guess = 0.0
num_guesses = 0

while abs(guess ** 2 - n) >= epsilon and guess <= n:
    guess = guess + step
    num_guesses = num_guesses + 1

if abs(guess ** 2 - n) >= epsilon:
    print(f'Failed to find sqrt({n})')
else:
    print(f'{guess} is close to sqrt({n})')
    print(f'Number of guesses: {num_guesses}')

# 4.999000000001688 is close to sqrt(25)
# Number of guesses: 49990

Roughly $n/\delta$ candidates are tested before the neighbourhood of $\sqrt{n}$ is reached, here $49{,}990$ of them. The answer is not $5$ : $4.999^2 = 24.990001$ is within $\varepsilon = 0.01$ of $25$ , which is all that was asked.

Example 3.30 (When the search space misses the answer).

Run the same program with $n = 0.25$ :

n = 0.25
epsilon = 0.01
step = 0.0001
guess = 0.0

while abs(guess ** 2 - n) >= epsilon and guess <= n:
    guess = guess + step

if abs(guess ** 2 - n) >= epsilon:
    print(f'Failed to find sqrt({n})')

# Failed to find sqrt(0.25)

The search fails because $\sqrt{0.25} = 0.5$ , while the guard guess <= n stops it at $0.25$ . The guard was written for $n \geqslant 1$ , where $\sqrt{n} \leqslant n$ ; for $0 < n < 1$ we have $\sqrt{n} > n$ and the upper bound has to be raised.

Example 3.31 (When the step is too large).

Now take $n = 123{,}456$ with the same $\delta = 0.0001$ . The program runs a long time and then reports failure: the step carries it over every value within $\varepsilon$ of $\sqrt{123456} \approx 351.363$ without ever landing on one. Shrinking $\delta$ to $10^{-6}$ repairs that and obliges the program to test some $351{,}000{,}000$ candidates. Starting nearer the answer would help, and presumes we already know roughly where the answer is.

The step $\delta$ controls both the accuracy and the running time, in opposite directions: a smaller step is more accurate and slower.

Bisection Search

Exhaustive enumeration does not use whether $\hat{x}^2$ was too small or too large. Bisection uses that comparison to discard half the remaining candidates at every step.

Looking up a word in a dictionary works the same way: open it near the middle, and if the word comes later than the page shown, discard the first half and open the second half near its middle.

We state the algorithm on an interval, in the notation of the first lesson.

Definition 3.32 (Bisection search).

Let $f$ preserve order on $[\ell, h]$ , so that $a < b$ implies $f(a) < f(b)$ throughout. Bisection search solves $f(x) = y$ by maintaining the invariant that a solution lies in $[\ell, h]$ and halving the interval:

compute the midpoint $m = (\ell + h)/2$ ;
if $f(m)$ is too large, replace $h$ by $m$ ; if $f(m)$ is too small, replace $\ell$ by $m$ ;
repeat until $|f(m) - y| < \varepsilon$ .

After $k$ steps the interval has width $(h_0 - \ell_0)/2^{k}$ , where $h_0 - \ell_0$ is its initial width.

Figure 3.3. The first six steps of a bisection search for

\sqrt{25}

[0, 25]

. Each bar is the interval still under consideration, the dot on it is the midpoint tested, and the dashed line marks the root at

x = 5

Implementation

n = 25
epsilon = 0.01
low = 0.0
high = max(1.0, n)
guess = (low + high) / 2.0
num_guesses = 0

while abs(guess ** 2 - n) >= epsilon:
    num_guesses = num_guesses + 1
    if guess ** 2 < n:
        low = guess
    else:
        high = guess
    guess = (low + high) / 2.0

print(f'{guess} is close to sqrt({n})')
print(f'Number of guesses: {num_guesses}')

# 5.00030517578125 is close to sqrt(25)
# Number of guesses: 13

Exhaustive enumeration needed about fifty thousand guesses; bisection needs thirteen. The upper end is max(1.0, n) rather than n, so that $\sqrt{n}$ lies in $[0, h]$ whether $n \geqslant 1$ or $0 < n < 1$ , which repairs the failure on $n = 0.25$ .

Example 3.33 (Hand simulating the bisection).

The first four steps for $\sqrt{25}$ on $[0, 25]$ :

Step	`low`	`high`	`guess`	`guess ** 2`	Action
0	0.0	25.0	12.5	156.25	too high, `high = 12.5`
1	0.0	12.5	6.25	39.0625	too high, `high = 6.25`
2	0.0	6.25	3.125	9.765625	too low, `low = 3.125`
3	3.125	6.25	4.6875	21.972656	too low, `low = 4.6875`

Four steps have taken the interval from width $25$ to width $6.25 - 4.6875 = 1.5625$ , and eight more bring it below $0.01$ .

Example 3.34 (Bisection on a larger input).

Exhaustive approximation failed on $n = 123{,}456$ because no step served: too large and it skipped the root, too small and it needed hundreds of millions of guesses. Bisection starts from $[0, 123456]$ and, by the theorem below, needs at most $\lceil \log_2(123456/0.01)\rceil = \lceil \log_2 12{,}345{,}600 \rceil = 24$ guesses to narrow the interval that far. Run, it stops after $30$ , the excess coming from the test being on $|\hat{x}^2 - n|$ rather than on the width of the interval.

Convergence

Bisection produces guesses $m_0, m_1, m_2, \ldots$ , and each step halves the interval holding the root, so the distance from the guess to the root falls by a factor of two every time. The bound this gives is stated with the logarithm to base $2$ , written $\log_2 N$ : the power to which $2$ must be raised to give $N$ , so that $\log_2 8 = 3$ and $\log_2 1024 = 10$ , and $\log_2 2500 \approx 11.29$ for an $N$ that is not a power of two.

Theorem 3.35 (Convergence of bisection search).

Let $[a, b]$ be the initial interval and $\varepsilon > 0$ the tolerance. Bisection search narrows the interval below $\varepsilon$ after at most $\lceil \log_2((b-a)/\varepsilon)\rceil$ steps.

Discussion.

The proof follows the width of the interval. One step replaces the interval by one of its two halves, so the width is halved whichever half survives, and after $k$ steps it is the initial width divided by $2^k$ . It remains to find the least $k$ for which this is below $\varepsilon$ , by taking $\log_2$ of both sides; the ceiling appears because $k$ counts steps and must be an integer. The argument resembles the one for decrementing functions, with a width halved at each step in place of a counter decreased by one, and so the number of steps is logarithmic rather than linear.

Proof.

Each step replaces $[\ell, h]$ by either $[\ell, m]$ or $[m, h]$ with $m$ the midpoint, so the new width is half the old one. After $k$ steps the width is therefore $(b-a)/2^{k}$ , and since the midpoint of an interval of width $w$ is within $w/2$ of every point of it, the guess is within $(b-a)/2^{k+1}$ of the root.

We need $(b-a)/2^{k} < \varepsilon$ , that is $2^{k} > (b-a)/\varepsilon$ , that is

k > \log_2\!\left(\frac{b-a}{\varepsilon}\right) .

The least integer meeting this is $\lceil \log_2((b-a)/\varepsilon)\rceil$ .

Example 3.36 (Checking the bound).

For $\sqrt{25}$ on $[0, 25]$ with $\varepsilon = 0.01$ the theorem gives

\left\lceil \log_2\!\left(\frac{25}{0.01}\right) \right\rceil = \lceil \log_2 2500 \rceil = \lceil 11.29 \rceil = 12 ,

and the program used $13$ : the test is on $|\hat{x}^2 - n|$ rather than on the width, and floating-point rounding can add a step.

Remark (Logarithmic against linear).

Exhaustive enumeration with step $\delta$ tests about $n/\delta$ candidates; bisection tests about $\log_2(n/\varepsilon)$ . For $n = 10^9$ and $\varepsilon = 0.01$ that is of the order of $10^{11}$ guesses against roughly $37$ . Doubling the range doubles the work of the first and adds a single step to the second.

Problem 3.22.

Adapt the bisection program to approximate $\sqrt[3]{27}$ to within $\varepsilon = 0.001$ . How many guesses does it need? Compare that with the number exhaustive enumeration with step $\delta = 0.001$ would need, and with the bound of the theorem.

Machine Arithmetic

The methods above assume that arithmetic on reals is exact: that $0.1 + 0.1 + 0.1$ is $0.3$ , that halving an interval halves it, and that the only error is the tolerance we chose. On a machine none of these holds exactly.

Binary Fractions

A computer stores numbers in binary. Just as the decimal system writes fractions with negative powers of ten, so that $0.375 = 3/10 + 7/100 + 5/1000$ , the binary system uses negative powers of two:

(0.b_1 b_2 b_3 \ldots)_2 = \frac{b_1}{2} + \frac{b_2}{4} + \frac{b_3}{8} + \cdots .

Example 3.37 (Exact binary fractions).

The decimal $0.375$ has an exact binary form:

0.375 = \frac{1}{4} + \frac{1}{8} = 0 \cdot \tfrac{1}{2} + 1 \cdot \tfrac{1}{4} + 1 \cdot \tfrac{1}{8} = (0.011)_2 .

Likewise $0.5 = (0.1)_2$ and $0.625 = 1/2 + 1/8 = (0.101)_2$ . These are exact because their denominators are powers of two: $0.375 = 3/8$ , $0.5 = 1/2$ and $0.625 = 5/8$ .

Not every decimal fraction has a finite binary form.

Theorem 3.38 (One tenth is not a finite binary fraction).

The number $1/10$ has no finite binary representation.

Discussion.

A finite binary fraction has a power of two as its denominator, and the proof compares that with the factor $5$ in $10$ . Suppose the representation existed with $k$ bits. Multiplying it through by $2^{k}$ clears every denominator at once and leaves an integer on the right, so the supposed identity becomes $2^{k} = 10M$ for an integer $M$ . The right-hand side is divisible by $5$ and the left is a power of two, and no power of two has $5$ among its factors. The same argument gives the general case: a fraction in lowest terms is a finite binary fraction exactly when its denominator is a power of two.

Proof.

Suppose $1/10 = (0.b_1 b_2 \ldots b_k)_2$ for some bits $b_1, \ldots, b_k$ . Then

\frac{1}{10} = \frac{b_1}{2} + \frac{b_2}{4} + \cdots + \frac{b_k}{2^{k}} = \frac{M}{2^{k}}, \qquad M = b_1 2^{k-1} + b_2 2^{k-2} + \cdots + b_k \in \mathbb{N}_0 .

Cross-multiplying gives $2^{k} = 10M$ , so $5$ divides $2^{k}$ . But $2^{k}$ is a product of $k$ factors of $2$ , and $5$ is a prime different from $2$ , so $5$ divides no power of $2$ . The supposition is therefore false.

The same holds in general: a rational $p/q$ in lowest terms has a finite binary expansion exactly when $q$ is a power of two, and since $10 = 2 \cdot 5$ , the fraction $1/10$ needs an infinite repeating binary expansion, just as $1/3 = 0.333\ldots$ repeats for ever in decimal.

What This Costs in Practice

Python’s float uses the IEEE 754 double-precision format: $64$ bits carrying a sign, an $11$ -bit exponent and a $52$ -bit significand with one further bit implied. That is about $15$ to $17$ significant decimal digits.

The consequence is that a decimal constant which looks exact in the source is silently rounded to the nearest representable binary fraction. Putting the format specifier :.20f inside an f-string prints twenty digits after the point and exposes it:

print(0.1)              # 0.1                     (the display is rounded)
print(f'{0.1:.20f}')    # 0.10000000000000000555

print(0.1 + 0.1 + 0.1 == 0.3)     # False
print(f'{0.1 + 0.1 + 0.1:.20f}')  # 0.30000000000000004441
print(f'{0.3:.20f}')              # 0.29999999999999998890

The sum overshoots by about $5.5 \times 10^{-17}$ , while the literal 0.3 is itself rounded downwards from three tenths. The two errors go opposite ways, so == returns False.

Example 3.39 (A loop that never lands).

Counting from $0$ to $1$ in steps of a tenth:

x = 0.0
count = 0

while x != 1.0:
    x = x + 0.1
    count = count + 1
    if count > 20:
        print('Gave up')
        break

The loop never stops of its own accord. After ten additions x is 0.9999999999999999, not 1.0; the eleventh takes it to 1.0999999999999999, and it has stepped over 1.0 without touching it. Replacing != by < 1.0, or by abs(x - 1.0) >= epsilon, repairs it.

Remark (Never compare floats with $==$).

Do not test floating-point numbers for exact equality. The expression x == 0.3 is almost certainly wrong even when x was computed by a formula mathematically equal to three tenths. Test instead that the difference is small:

x = 0.1 + 0.1 + 0.1
print(abs(x - 0.3) < 1e-9)   # True

This is an $\varepsilon$ -approximation applied to equality; the tolerance should match the precision of the computation, not of the display.

Example 3.40 (Rounding error accumulates).

Adding a tenth a thousand times:

total = 0.0

for i in range(1000):
    total = total + 0.1

print(f'{total:.20f}')     # 99.99999999999859312538
print(total == 100.0)      # False
print(abs(total - 100.0))  # about 1.4e-12

Each addition contributes a rounding error of the order of $10^{-17}$ , and over a thousand additions they accumulate to about $10^{-12}$ : small, but enough to make an exact test fail.

Remark (When it matters).

For the bisection search this error is harmless: an approximate answer was wanted, and $\varepsilon$ is much larger than the rounding. The problem arises in code that assumes exact arithmetic, by testing x == 0.0 where it should test abs(x) < epsilon, or by expecting a counter incremented by 0.1 to arrive exactly at 1.0 after ten steps.

Problem 3.23.

The theorem above rules out $1/10$ , and the paragraph following it makes the general claim: a rational $p/q$ in lowest terms has a finite binary expansion exactly when $q$ is a power of two. Prove both directions, following the argument of the theorem. Then say how many bits the expansion of $p/2^{k}$ needs when $p$ is odd, and give the expansions of $7/16$ and $5/6$ as far as each can be written.

Problem 3.24.

The loop of the example above adds $0.1$ a thousand times and lands about $1.4 \times 10^{-12}$ short of $100$ .

Write a second program that adds the integer $1$ a thousand times and divides by ten at the end, and compare its result with 100.0 using ==.
Say why the second is exact where the first is not, in terms of which numbers have a finite binary expansion.
A sum of money is to be accumulated over many transactions, each an exact number of pounds and pence. Say which of the two arrangements should be used, and what the other would cost after a million transactions.

Exercises on Types and Expressions

Exercise 3.1.

Give the type and the value of each expression.

7 / 2;
7 // 2;
7 % 2;
7.0 // 2;
2 ** 0.5;
1 == 1.0.

Exercise 3.2.

State the value of 2 ** 3 ** 2, (2 ** 3) ** 2, -2 ** 2 and (-2) ** 2, and say which rule of precedence or associativity settles each one.

Exercise 3.3.

Predict the value of 0.1 + 0.2 == 0.3 and of 0.5 + 0.25 == 0.75, then check both. Explain why the two come out differently, and give another pair of float values whose sum can be tested exactly.

Exercise 3.4.

Let n be a positive integer.

Write an expression for its last two decimal digits.
Write an expression for the digit in its hundreds place.
Write an expression that is True exactly when n is a multiple of $3$ but not of $9$ .

Exercise 3.5.

Give the value of int('101', b) for $b = 2, 3, 8$ and $16$ , and find the base $b$ for which it equals $122$ .

Exercise 3.6.

Explain why x != 0 and 100 % x == 0 may be evaluated for any integer x, while 100 % x == 0 and x != 0 may not.

Exercise 3.7.

Explain what a, b = b, a does, and why performing a = b and then b = a does not do the same. Say what the second pair leaves in a and b.

Exercises on Branching

Exercise 3.8.

Write a program that reads three integers and prints them in increasing order, using conditional statements only and no built-in sorting.

Exercise 3.9.

A year is a leap year when it is divisible by $4$ , except that centuries are not, except that those divisible by $400$ are. Write a program that reads a year and reports whether it is a leap year, and check it on $1900$ , $2000$ , $2023$ and $2024$ .

Exercise 3.10.

Write a program that reads a real number x and prints which of the intervals $(-\infty, -1)$ , $[-1, 0)$ , $[0, 1]$ and $(1, \infty)$ contains it.

Exercise 3.11.

Write a program that reads three numbers a, b and c and prints how many of them are strictly positive. Use branching only, with no loop and no arithmetic on the results of the tests.

Exercise 3.12.

The expressions 1/x if x != 0 else 0 and (x != 0) * (1/x) agree for every non-zero x. Say what each does when x is 0, and explain the difference in terms of which arms of a case split get evaluated.

Exercise 3.13.

Explain why a branching program of $N$ statements performs at most $N$ atomic operations on any input, and give a three-statement program whose count of operations depends on its input.

Exercise 3.14.

Write a program that reads three positive reals and reports whether they can be the side lengths of a triangle, that is, whether each of them is smaller than the sum of the other two. Use conditional statements only.

Exercises on Iteration

Exercise 3.15.

Write a program that computes $n!$ for a given $n \geqslant 0$ with a for loop, and a second that does the same with a while loop. State how many multiplications each performs, and say what each returns for $n = 0$ .

Exercise 3.16.

Write a program that counts the digits of $n$ in base $b$ with a loop, for $n \in \mathbb{N}$ and $b > 1$ . Check its count against Corollary 2.22 for several $n$ and $b$ .

Exercise 3.17.

Write a program that sums the decimal digits of a positive integer using // and % only, with no strings. Extend it to repeat the process on the result until a single digit is left, and compare that digit with $n \bmod 9$ .

Exercise 3.18.

Write a program that prints the first $n$ Fibonacci numbers, using a single multiple assignment inside the loop to advance the pair.

Exercise 3.19.

Write a program that takes positive integers $a$ and $b$ and repeatedly replaces the pair by the smaller number and the remainder of the larger on division by it, stopping when the remainder is $0$ . Hand simulate the loop on $(48, 18)$ , and identify the surviving number as the largest integer dividing both $a$ and $b$ .

Exercise 3.20.

Write a program that prints every pair $(a, b)$ with $1 \leqslant a < b \leqslant N$ and $a \mid b$ , for a given $N$ . Say how many divisibility tests it performs as a function of $N$ .

Exercise 3.21.

Modify the trial-division program so that, when $n$ is composite, it also prints the least divisor of $n$ above $1$ . Run it on three numbers near one million of your own choosing, and say which of them are prime.

Exercise 3.22.

Write a program that converts a string of base- $b$ digits to an integer with a loop, for a given $b > 1$ , using Horner’s scheme rather than forming any power of $b$ . Count the multiplications, and check the result against int.

Exercise 3.23.

Write a program that runs the loop replacing $n$ by $n/2$ when $n$ is even and by $3n + 1$ when $n$ is odd, stopping when $n$ reaches $1$ , and counts its passes. Run it on each starting value from $1$ to $30$ , and report which takes the most.

Exercises on Running Time

Exercise 3.24.

Show directly from the definition that $\sum_{k=1}^{n} k = O(n^2)$ , giving an explicit $\alpha$ and $n_0$ , and that $n^2 = O\bigl(\sum_{k=1}^{n} k\bigr)$ as well, so that each of the two is $O$ of the other. Then do both again with the limit form.

Exercise 3.25.

Decide which of the following hold, with a proof or a counterexample in each case.

$2^{n+1} = O(2^n)$ ;
$2^{2n} = O(2^n)$ ;
$\log_2 n = O(\log_{10} n)$ ;
$n\log_2 n = O(n^2)$ .

Exercise 3.26.

Suppose $f_1 = O(g)$ and $f_2 = O(g)$ . Prove that $f_1 + f_2 = O(g)$ and that $c\,f_1 = O(g)$ for every constant $c > 0$ . Then give functions with $f_1 = O(g)$ and $f_2 = O(g)$ for which $f_1 f_2 = O(g)$ fails, so that $O$ is closed under sums and constant multiples but not under products.

Exercise 3.27.

An input of $n$ decimal digits denotes a number of size about $10^n$ . Express the running time of trial division as a function of the number of digits of its input rather than of the number itself, and say how many digits a number may have before an algorithm performing $10^9$ operations a second needs more than an hour.

Exercise 3.28.

Count the elementary operations performed by the schoolbook algorithms on two $n$ -digit numbers exactly, rather than up to $O$ : give the number of single-column additions performed by the addition, and the number of single-digit multiplications performed by the multiplication.

Exercises on Search and Approximation

Exercise 3.29.

Give a decrementing function for each of the following loops and state the bound on the number of passes it yields.

while n >= 10: n = n // 10, for $n \in \mathbb{N}$ ;
while a != b: a, b = (a - b, b) if a > b else (a, b - a), for positive integers $a$ and $b$ ;
the exhaustive square-root search of this chapter, whose body is guess = guess + step.

Exercise 3.30.

The positions of a string are numbered from $0$ . Write a program that prints the characters of a string my_str at the even positions, so that 'abcdefg' produces aceg. Write it twice, once with range and indexing, and once with a for loop over the characters and a counter.

Exercise 3.31.

Let $N$ be an integer with $0 \leqslant N \leqslant 1000$ . Write a program that finds $N$ by bisection search, printing the number of guesses it needed and the value found. When the midpoint of the current interval falls between two integers, take the smaller.

Exercise 3.32.

A positive integer $n$ is a perfect power if $n = r^{p}$ for integers $r \geqslant 1$ and $p \geqslant 2$ . Write a program that reads $n$ and prints integers root and pwr with $1 < \text{pwr} < 6$ and $\text{root}^{\text{pwr}} = n$ , or reports that no such pair exists. Test it on $64$ , which admits $8^2$ , $4^3$ and $2^6$ , on $27$ , and on $72$ .

Exercise 3.33.

Write a program that approximates $\log_2 x$ for a positive real $x$ to within $\varepsilon = 0.001$ by bisection. It must first find an interval $[L, H]$ containing $\log_2 x$ : note that $2^0 = 1$ , that $2^{k}$ grows without bound, and that $2^{-k}$ becomes arbitrarily small, so $L$ may have to be negative. Test it on $x = 1$ , $x = 32$ and $x = 0.1$ .

Exercise 3.34.

Run the exhaustive square-root search and the bisection search on the same $n$ for $\varepsilon = 10^{-2}, 10^{-4}$ and $10^{-6}$ , recording the number of guesses each makes. Say which of the two counts grows with $1/\varepsilon$ and which with $\log(1/\varepsilon)$ , and check the readings against the two bounds.

Exercise 3.35.

Find two float values a and b for which (a + b) + c and a + (b + c) differ for some c, and explain the difference in terms of rounding. What does this say about summing a list of numbers in different orders?

Exercise 3.36.

Which of the decimals $0.5$ , $0.2$ , $0.25$ , $0.3$ and $0.125$ are exact as float values? Predict the answer from the theorem on binary fractions before checking each with :.20f.

An Applied Exercise

Exercise 3.37.

A band puts $N = 5000$ tickets on sale for one night and prices them dynamically. The first ticket costs $p_0 = \pounds 40.00$ . The tickets are sold in blocks of $k = 250$ , and after each block the price is raised by $r = 8\%$ of the current price. The band will not charge more than a cap of $C = \pounds 120.00$ : once a rise would take the price above the cap, the price is set to the cap and stays there for every remaining block.

Write a program that sells all $N$ tickets under this rule and prints the price of each block together with the total revenue. Report the revenue.
Give, in terms of $p_0$ , $r$ and $C$ , the number of rises after which the uncapped price would first exceed the cap, and hence the number of the first block sold at the cap. Check your formula against the output of your program.
Consider the sequence of price increases between consecutive blocks. Show that before the cap binds these form a geometric sequence and give its ratio. Exactly one increase belongs to neither the geometric stretch nor the capped stretch: identify it, give its value, and say what it would have been without the cap.
Show that once the cap binds the total revenue is a linear function of the number of tickets sold, and give its slope. Say what the revenue would look like as a function of $N$ if the cap were removed.
Give the running time of your program in $O$ notation as a function of $N$ and $k$ , and say which of the two the running time really depends on.
Prices in pounds are not exact float values. Rewrite the simulation in integer pence, rounding each new price down to the nearest penny, and compare the two totals. The two disagree for two separate reasons; say which reason accounts for most of the gap, and which of the two totals the band should quote.

Check Yourself

Fresh questions on the whole lesson — none of them is worked out above. Work each one out on paper or in your head before opening Python; the box only tells you whether you got there.

Answers are checked in your browser, as often as you like. Nothing is sent anywhere and nothing is kept but your own work. A formula may be written with the symbols themselves or with ~ & | -> <-> ^, and \and, \or, \to expand as you type.

Lesson 4

Data Structures and Graphs

Taught 04 Sept 2026

Data Structures

Every program of the last lesson held a bounded number of values at once: a guess, a counter, a running total, the string being built up. A program that has to keep many values, for example to sort a list of numbers or to remember which candidates have been ruled out, needs somewhere to store them and a way to reach any one of them. A data structure is such a place together with the operations for using it.

We compare algorithms by explicit models of cost, and refine an implementation only once the broad algorithmic choice has been made. For every algorithm there are two things to prove: that it terminates, and that it is correct, meaning that the output it returns is a correct output for its input in the sense of a computational problem.

Functions

From here on an algorithm is usually written as a function: a named piece of code that takes inputs, called its arguments, and returns an output.

def square(x):
    return x * x

print(square(7))       # 49
print(square(-3) + 1)  # 10

The line def square(x): names the function and its parameter x; the indented body is its code. A call square(7) binds the parameter x to the argument 7, runs the body, and evaluates to the value named by return, which ends the call at once. A function whose body finishes without reaching a return returns None. Names bound inside the body are local: they exist only while that call runs and do not disturb names of the same spelling elsewhere.

def smallest(a, b, c):
    target = a
    if b < target:
        target = b
    if c < target:
        target = c
    return target

target = 100
print(smallest(4, -2, 9))   # -2
print(target)              # 100, untouched by the call

A function may return several values at once as a tuple, and the caller may unpack them by multiple assignment: return p, q and then p, q = f(p, q).

In pseudocode we give a function a name and write its arguments in brackets, as in Fact(n), and return has its Python meaning.

Recursion

A function may call itself. The call f(n) then waits while f(n - 1) runs, and that call has its own local names, separate from those of the call that made it. The part of memory that keeps track of this is organised as a stack: each call places a frame holding its local names on top, and returning removes the top frame, so the most recent call is always the first to finish. The number of frames present at once is the depth of the recursion.

Recursion needs a case that does not call the function again, reached after finitely many calls; otherwise the stack grows until Python stops the program with a RecursionError.

def count_down(n):
    if n == 0:
        print('done')
    else:
        print(n)
        count_down(n - 1)

count_down(3)   # 3, 2, 1, done

Problem 4.1.

Write a function digit_sum(n) that returns the sum of the decimal digits of a positive integer $n$ , once with a while loop and once recursively, using // and % only. State the depth of the recursion in terms of $n$ .

Induction and Loop Invariants

For a statement $P(n)$ about every nonnegative integer, proof by induction has two parts: prove $P(0)$ , then assume $P(n)$ for an arbitrary $n$ and use that assumption to prove $P(n+1)$ . If the statement begins at $n = 1$ , start with $P(1)$ . The base case gives $P(0)$ , and the step then gives $P(1)$ , $P(2)$ and so on. The last lesson used this pattern for the closed forms of recurrences; we now use it for recursive algorithms and for loops.

Definition 4.1 (Loop invariant).

A loop invariant is a statement about the program state that

holds before the first iteration (initialisation),
is preserved by every iteration (maintenance), and
gives the desired conclusion when the loop stops (use at termination).

An invariant plays the part of the induction hypothesis: initialisation is the base case, and maintenance is the step. It says nothing about whether the loop stops. That is proved separately by a decrementing function, often called a variant in this context.

Theorem 4.2 (Chocolate-bar strategy).

A rectangular chocolate bar has a marked corner square. A move removes a nonempty strip by one horizontal or vertical cut, retaining the piece containing the marked square. The player who receives the $1 \times 1$ bar loses. The first player has a winning strategy exactly when the starting rectangle is not a square.

Discussion.

Write $(p, q)$ for the current numbers of rows and columns. The strategy is to hand the opponent a square every time: from a nonsquare, cut the longer side down to the shorter. The invariant is the pair of facts that the strategy user always receives a nonsquare and always hands over a square; initialisation is the starting position, and maintenance holds because every legal move from a square produces a nonsquare. The product $pq$ falls with every move, so it serves as the variant and play reaches $(1, 1)$ . Since $(1, 1)$ is a square, the strategy user never receives it. The two cases of the statement say which player can use the strategy.

Proof.

Write $(p, q)$ for the current positive numbers of rows and columns. If $p \neq q$ , the player to move can cut the larger coordinate down to the smaller one and hand the other player a square. Every legal move from a square changes exactly one coordinate, so it makes the coordinates unequal; the next player can therefore make a square again. The invariant is that the player using this strategy always receives a nonsquare rectangle and always hands over a square.

Every move strictly reduces the positive integer $pq$ , so play eventually reaches $(1, 1)$ . The strategy user cannot receive $(1, 1)$ , since that state is square. If the initial rectangle is nonsquare, Player One uses the strategy; if it is square, Player Two uses it after Player One’s first cut.

Example 4.3 (A game from $(5, 3)$ ).

Starting from $(5, 3)$ , Player One cuts to $(3, 3)$ . If the opponent cuts to $(3, 1)$ , Player One cuts to $(1, 1)$ and the opponent loses.

One full round can be implemented as a loop: check whether Player One has received $(1, 1)$ , let Player One move, check whether the opponent has received $(1, 1)$ , then let the opponent move. Player One’s move is the square-producing cut:

Player One's Move
Input:  the numbers p, q of rows and columns of the retained rectangle.
Output: the rectangle after the move.

    if p > q then p ≝ q
    else if q > p then q ≝ p
    else p ≝ p − 1
    return p, q

def player(p, q):
    if p > q:
        p = q
    elif q > p:
        q = p
    else:
        p = p - 1   # reached only from a square
    return p, q

For a nonsquare starting position, the last branch is never reached under the winning strategy. The opponent may choose any legal cut; the proof above covers all such choices.

Recursive and Iterative Factorials

Recursive and iterative factorial functions show the connection between induction and invariants. Define $0! = 1$ and $n! = n \cdot (n-1)!$ for $n > 0$ .

Recursive Factorial                    Iterative Factorial
Input:  n ∈ N₀.                        Input:  n ∈ N₀.
Output: n!.                            Output: n!.

    Fact(n):                               r ≝ 1
        if n = 0 then return 1             for j ≝ 1 to n do r ≝ r · j
        else return n · Fact(n − 1)        return r

The recursive version returns $1$ at $n = 0$ and otherwise returns $n \cdot \mathrm{Fact}(n-1)$ ; induction on $n$ proves it correct, the base case being the first branch and the step the second. The iterative version begins with $r = 1$ and multiplies $r$ by $j$ for $j = 1, \ldots, n$ . Before iteration $j$ the invariant is $r = (j-1)!$ ; after the multiplication it becomes $r = j!$ , so at exit $r = n!$ . The variant $n - j + 1$ decreases to zero.

def fact_recursive(n):
    if n == 0:
        return 1
    return n * fact_recursive(n - 1)

def fact_iterative(n):
    r = 1
    for j in range(1, n + 1):
        r = r * j
    return r

print(fact_recursive(10), fact_iterative(10))   # 3628800 3628800

The recursive version has depth $n + 1$ : the call for $n$ waits on the call for $n - 1$ , down to $0$ . The iterative version uses a single frame. Python integers have no fixed size, so both return $n!$ exactly however large it is. A product of large integers is then not an elementary operation, and costs what the schoolbook bound says.

Problem 4.2.

The loop below is meant to compute $a^n$ for an integer $a$ and $n \in \mathbb{N}_0$ with about $\log_2 n$ multiplications.

def power(a, n):
    result, base, e = 1, a, n
    while e > 0:
        if e % 2 == 1:
            result = result * base
        base = base * base
        e = e // 2
    return result

Show that $\text{result} \cdot \text{base}^{\,e} = a^n$ is a loop invariant, give a variant, and deduce that power is correct. How many multiplications does it perform, in terms of the binary expansion of $n$ ?

Problem 4.3.

In the chocolate-bar game a move may instead remove a strip of width one or two only. Decide, for each starting rectangle $(p, q)$ with $1 \leqslant p, q \leqslant 4$ , which player has a winning strategy, and state and prove a rule covering every $(p, q)$ .

Measuring Cost

A program can spend most of its running time in a small part of its code. Choosing a better algorithm for that part usually does more than rewriting individual instructions, and much of the low-level rewriting is done automatically in any case by the software that translates a program into machine instructions. Costs other than time and memory can matter too, energy and money among them. For example, a “Penny Sort” measure asks how many externally stored records can be sorted for a US cent, after the purchase cost of a fixed machine is spread over an assumed working life. That measure combines hardware cost and algorithm throughput.

Example 4.4 (Which method is faster depends on $n$ ).

Suppose method A uses exactly $100n$ operations on an input of size $n$ , while method B uses exactly $n^2$ . At $n = 10$ , A uses $1000$ operations and B uses $100$ ; at $n = 1000$ , A uses $100{,}000$ and B uses $1{,}000{,}000$ . The method with fewer operations depends on the input size, and the two cross at $n = 100$ .

The running time of the last lesson counted elementary operations. We also measure memory.

Definition 4.5 (Time cost and auxiliary space).

The time cost of an algorithm counts operations in a stated model. Its auxiliary space, or memory footprint, is the maximum amount of extra storage present at any instant of a run, excluding the input.

Storage may be released and reused later, which is why the footprint is a maximum and not a cumulative total. In a conventional model allocating or touching a memory cell costs at least one operation, so an algorithm’s footprint cannot exceed a constant multiple of its running time. This claim depends on the model, and it does not say that every algorithm uses as much space as time.

The unit-cost assumption has to be stated with care. A comparison of two strings is not necessarily a single operation: it may inspect many characters. A comparison of two integers of bounded size is commonly counted as one operation, but for arbitrarily large integers or variable-length records the cost must be stated.

Lower and Two-Sided Bounds

Landau’s $O$ from the last lesson is an upper bound. It has a lower counterpart, and the two together give a two-sided bound.

Definition 4.6 ( $\Omega$ and $\Theta$ ).

Let $f, g : \mathbb{N} \to \mathbb{R}_{\geqslant 0}$ . We write

\begin{aligned} f &= \Omega(g) &&\text{if there are } c > 0 \text{ and } n_0 \text{ with } c\,g(n) \leqslant f(n) \text{ for all } n \geqslant n_0, \\ f &= \Theta(g) &&\text{if } f = O(g) \text{ and } f = \Omega(g). \end{aligned}

As with $O$ , the equals sign is shorthand for membership of a set of functions, not equality of functions. The last lesson wrote $f = o(g)$ , read ” $f$ grows strictly more slowly than $g$ ”, when $f(n)/g(n)$ tends to zero. Written out without limits: $g(n) > 0$ from some point on, and for every $\varepsilon > 0$ there is an $n_0$ with $f(n) \leqslant \varepsilon\, g(n)$ for every $n \geqslant n_0$ . This is stronger than $f = O(g)$ , since the constant multiplier can be made as small as we wish by taking $n$ large enough.

The growth rates met most often are, from slowest to fastest,

\log n, \quad n, \quad n \log n, \quad n^{3/2}, \quad n^2, \quad n^3, \quad 2^n .

Logarithm bases differ only by a constant factor, since $\log_a n = \log_b n / \log_b a$ by the change of base; so $\Theta(\log_2 n)$ and $\Theta(\log_{10} n)$ are the same class and the base is usually left off.

Problem 4.4.

Show that $\tfrac12 n^2 - 3n = \Theta(n^2)$ by exhibiting the constants, and that $n \log_2 n = o(n^2)$ .

Lower Bounds

The comparison model of computation acts on a set of comparable objects. The objects are treated as black boxes supporting only binary tests called comparisons, namely $<$ , $\leqslant$ , $>$ , $\geqslant$ , $=$ and $\neq$ : each takes two objects and returns True or False according to their relative order. Nothing else about the objects may be inspected, so an algorithm in this model learns about its input only through the answers to comparisons, and its cost is counted as the number of comparisons it makes.

Definition 4.7 (Problem lower bound and optimality).

A problem lower bound is a bound that applies to every algorithm solving the problem in a specified model. An algorithm is asymptotically optimal for a cost measure when its upper bound matches the problem’s lower bound up to constants.

An upper bound is about one algorithm, and a lower bound is about every algorithm for the problem. A lower bound therefore has to fix a model, which lists the operations an algorithm may use.

Proposition 4.8 (Finding a maximum).

Finding the position of the maximum among $n$ pairwise distinct, otherwise unordered comparable elements requires at least $n - 1$ comparisons in the comparison model, and $n - 1$ comparisons suffice.

Discussion.

For the lower bound we count losses: an element can be ruled out as the maximum only once it has been seen to be smaller than something, and one comparison produces exactly one loser. All $n - 1$ non-maximal elements must be ruled out, so at least $n - 1$ comparisons are needed. For the upper bound a single left-to-right scan with a running maximum makes one comparison per element after the first, and its invariant says that the stored index is maximal in the prefix scanned so far.

Proof.

Before an element can be ruled out as the maximum, it must lose a comparison against a larger element. One comparison can give a first loss to at most one candidate. All but the true maximum, namely $n - 1$ candidates, must be ruled out, so at least $n - 1$ comparisons are necessary.

A scan keeps the index of the largest element seen and compares each of the remaining $n - 1$ elements with it once; its invariant is that the stored index is maximal in the scanned prefix. Thus it meets the lower bound.

A second proof uses an adversary, an imagined opponent who may change the input as long as every answer already given stays true.

Proof.

Fix an input of distinct values $T[0], \ldots, T[n-1]$ and a nonmaximum element $T[j]$ . Suppose $T[j]$ is never compared with an element larger than itself. Change only its value, to one larger than every original value. Every comparison involving $T[j]$ previously had a smaller other operand, so its outcome stays the same; all other comparisons are unchanged. A deterministic comparison algorithm therefore follows the same sequence of branches and returns the same index. But $j$ is now the true maximum, a contradiction. Thus each nonmaximum element must lose a comparison, which gives $n - 1$ losses.

The scan in pseudocode and in Python:

Position of the Maximum
Input:  a sequence T[0], …, T[n − 1] of comparable elements, n ⩾ 1.
Output: an index k with T[k] maximal.

    k ≝ 0
    for i ≝ 1 to n − 1 do
        if T[i] > T[k] then k ≝ i
    return k

def arg_max(T):
    k = 0
    for i in range(1, len(T)):
        if T[i] > T[k]:
            k = i
    return k

print(arg_max((3, 9, 2, 9, 4)))   # 1

Python’s len(T) gives the length of a tuple, as it does for a string, and T[i] its entry at position i.

Problem 4.5.

Give an algorithm that finds both the maximum and the minimum of $n$ distinct elements with at most $\lceil 3n/2 \rceil - 2$ comparisons. Then use an adversary to show that at least $\lceil 3n/2 \rceil - 2$ comparisons are necessary.

The Word-RAM Model

To calculate the resources an algorithm uses we need to say how long a computer takes to perform basic operations. Fixing such a set of operations gives a model of computation, on which the analysis is then based. We use the $w$ -bit Word-RAM model, which treats a computer as a random-access array of machine words called memory, together with a processor that performs operations on that memory.

Definition 4.9 (Word-RAM).

A machine word is a sequence of $w$ bits, read as an integer in $\{0, \ldots, 2^w - 1\}$ . A Word-RAM processor performs each of the following in constant time:

addition, subtraction, multiplication, integer division, remainder, bitwise operations and comparisons of two machine words;
given a word $a$ , reading or writing the word stored in memory at address $a$ .

A machine word of $w$ bits can name at most $2^w$ addresses, so the processor can read and write at most $2^w$ locations of memory. When a problem’s input occupies $n$ machine words we therefore always assume a word size of $w > \log_2 n$ bits, or the machine could not reach all of its input. For comparison, a Word-RAM model of a byte-addressable $64$ -bit machine allows inputs of up to about $10^{10}$ gigabytes.

Arrays

An array is a fixed number of storage slots in a row, numbered from $0$ , any of which may be read or written in a single elementary operation. The $i$ th slot of an array $p$ is written $p[i]$ . In the Word-RAM an array of $n$ words is a block of $n$ consecutive addresses, and reaching $p[i]$ means reading the address of $p[0]$ plus $i$ : one addition and one read, whatever $i$ is and whatever the length of $p$ .

Python Lists

Python’s counterpart of an array is a list, written in square brackets. A list is a sequence like a tuple, but its entries may be changed.

p = [3, 1, 4, 1, 5]
print(len(p), p[0], p[4])   # 5 3 5
p[1] = 9
print(p)                    # [3, 9, 4, 1, 5]

q = [True] * 4              # [True, True, True, True]
r = [None] * 3              # [None, None, None]

Positions are numbered from $0$ , as they are for strings, and p[i] = x writes to position i. The expression [x] * n builds a list of n copies of x. Several further operations will be used below.

p.append(x) adds x at the end, and p.pop() removes the last entry and returns it; p.pop(i) removes and returns the entry at position i.
The slice p[i:j] is a new list holding the entries at positions i up to but not including j, with the same convention as for strings; p[i:] runs to the end and p[:j] starts at the beginning. Building a slice copies its $j - i$ entries.
p + q is a new list holding the entries of p followed by those of q.
The comprehension [f(a) for a in X] builds the list of values f(a) as a runs through X.
x is None tests whether x is the object None.

Unlike a tuple, a list can grow and shrink; how Python does this is described under dynamic arrays below. Used with a fixed length it behaves as an array.

Listing the Primes

Deciding whether one number is prime was a decision problem; listing the primes up to a bound is a general discrete computational problem. It is the first problem here whose best algorithm uses an array, and it has a much faster algorithm than testing each number for primality.

List of Prime Numbers
Input: n ∈ N.
Task:  compute all prime numbers p with p ⩽ n.

Running the trial-division test on each of $2, \ldots, n$ in turn settles it in $O(n\sqrt{n})$ operations. The sieve of Eratosthenes does better by never testing divisibility at all: it writes down every candidate, then crosses out the multiples of each survivor in turn. It uses an array $p$ indexed by $0, \ldots, n$ .

Example 4.10 (The sieve of Eratosthenes).

The algorithm marks every index as a candidate and then strikes out the multiples of each index that is still marked.

The Sieve of Eratosthenes
Input:  n ∈ N.
Output: all prime numbers less than or equal to n.

    for i ≝ 2 to n do p[i] ≝ "yes"
    for i ≝ 2 to n do
        if p[i] = "yes" then
            output i
            for j ≝ i to ⌊n / i⌋ do p[i · j] ≝ "no"

The inner loop starts at $j = i$ rather than at $j = 2$ : the multiples $i \cdot 2, \ldots, i \cdot (i-1)$ have a factor smaller than $i$ and were struck out already.

The running time depends on the total work of the inner loops, which is a sum of harmonic numbers, which have no closed form. What we need instead is a bound on them. The lower bound is not needed for the sieve; it is used for quicksort in the next lesson.

Proposition 4.11 (Bounds on the harmonic numbers).

For every $n \in \mathbb{N}$ ,

\tfrac12 \lfloor \log_2 n \rfloor \;\leqslant\; H_n \;\leqslant\; 1 + \log_2 n .

Discussion.

We group the terms into blocks between consecutive powers of two. The block running from $k = 2^t$ to $k = 2^{t+1}-1$ has $2^t$ terms, each at most $1/2^t$ and more than $1/2^{t+1}$ , so the block contributes between $\tfrac12$ and $1$ whatever $t$ is. The number of blocks needed to cover $1, \ldots, n$ is about $\log_2 n$ , and both bounds follow. At the top the last block may be incomplete: for the upper bound we enlarge the sum to the end of that block, and for the lower bound we drop it.

Proof.

Let $m = \lfloor \log_2 n \rfloor$ , so that $2^m \leqslant n < 2^{m+1}$ . For $t \geqslant 0$ the block of indices $2^t \leqslant k \leqslant 2^{t+1} - 1$ has $2^{t+1} - 2^t = 2^t$ terms, and each has $2^t \leqslant k < 2^{t+1}$ , so

\frac12 = 2^t \cdot \frac{1}{2^{t+1}} \;\leqslant\; \sum_{k=2^{t}}^{2^{t+1}-1} \frac{1}{k} \;\leqslant\; 2^t \cdot \frac{1}{2^t} = 1 .

Every term is positive, so enlarging the range of summation increases the sum and shrinking it decreases the sum. The blocks $t = 0, \ldots, m$ cover $1, \ldots, 2^{m+1} - 1 \geqslant n$ , and the blocks $t = 0, \ldots, m - 1$ cover $1, \ldots, 2^m - 1 \leqslant n$ . Hence

H_n \;\leqslant\; H_{2^{m+1}-1} = \sum_{t=0}^{m} \; \sum_{k=2^{t}}^{2^{t+1}-1} \frac{1}{k} \;\leqslant\; m + 1 \;\leqslant\; \log_2 n + 1, \qquad H_n \;\geqslant\; H_{2^{m}-1} = \sum_{t=0}^{m-1} \; \sum_{k=2^{t}}^{2^{t+1}-1} \frac{1}{k} \;\geqslant\; \frac{m}{2} .

Theorem 4.12 (The sieve is correct and runs in $O(n \log n)$ ).

The sieve of Eratosthenes outputs exactly the primes less than or equal to $n$ , and performs $O(n \log n)$ elementary operations.

Discussion.

Correctness and running time are proved separately.

Correctness has two directions. No prime is ever struck out, because an entry is written to only as $p[i \cdot j]$ with both $i$ and $j$ at least $2$ , and such an index is composite by definition. In the other direction every composite $k$ must be struck before the outer loop reaches it, and the index that strikes it is its least divisor above $1$ : that divisor is itself prime, so it still carries “yes” when the outer loop arrives at it, and its partner $k$ divided by it is large enough to fall in the range the inner loop covers. That the partner is at least the divisor is Proposition 3.14, which is why the inner loop may start at $j = i$ .

For the running time, the outer loop costs $O(n)$ by itself, and the inner loop belonging to $i$ runs at most $n/i$ times. Summing $n/i$ over $i$ gives $n$ times a harmonic sum, and the upper bound just proved turns that into $n\log_2 n$ .

Proof.

Correctness. An entry of $p$ is set to “no” only in the inner loop, where the index written to is $i \cdot j$ with $i \geqslant 2$ and $j \geqslant i \geqslant 2$ . Such an index is a product of two integers greater than $1$ and so is composite; hence no prime is ever struck out, and every prime $\leqslant n$ still carries “yes” when the outer loop reaches it and is output.

Conversely let $k \leqslant n$ be composite, and let $i$ be its least divisor with $i \geqslant 2$ . Then $i$ is prime: a divisor $d$ of $i$ with $1 < d < i$ would divide $k$ as well and contradict minimality. By Proposition 3.14, $i \leqslant \sqrt{k}$ , so writing $j = k / i$ we have

j = \frac{k}{i} \;\geqslant\; \frac{k}{\sqrt{k}} = \sqrt{k} \;\geqslant\; i, \qquad j = \frac{k}{i} \leqslant \frac{n}{i},

and $j$ is an integer, so $i \leqslant j \leqslant \lfloor n/i \rfloor$ . Since $i$ is prime it is not struck out, so when the outer loop reaches $i$ the test succeeds and the inner loop runs, setting $p[i \cdot j] = p[k]$ to “no”. Finally $i \leqslant \sqrt{k} < k$ , so this happens before the outer loop reaches $k$ , and $k$ is not output. The algorithm therefore outputs the primes and nothing else.

Running time. The first loop performs $n - 1$ assignments. In the second loop, each of the $n-1$ values of $i$ costs a bounded amount for the test and the output, contributing $O(n)$ in total. The inner loop belonging to $i$ runs only when $p[i]$ is “yes”, and then makes at most $\lfloor n/i \rfloor - i + 1 \leqslant n/i$ passes, each of bounded cost. Summing over $i$ ,

\sum_{i=2}^{n} \frac{n}{i} = n\left(H_n - 1\right) \leqslant n \log_2 n

by the previous proposition. Adding the three contributions, the running time is $O(n) + O(n\log_2 n) = O(n \log n)$ .

In Python the array $p$ is a list of n + 1 entries, True for “yes” and False for “no”; positions $0$ and $1$ are never read.

def sieve(n):
    p = [True] * (n + 1)
    primes = []
    for i in range(2, n + 1):
        if p[i]:
            primes.append(i)
            for j in range(i, n // i + 1):
                p[i * j] = False
    return primes

print(sieve(50))
# [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]

Problem 4.6.

Count the assignments p[i * j] = False performed by the sieve for $n = 50$ , and compare the count with the bound $n\log_2 n$ of the theorem. Then count how many of them write “no” to an entry that was already “no”, and say which composite numbers are struck more than once.

Problem 4.7.

Modify the sieve so that the inner loop starts at $j = 2$ rather than $j = i$ . Show that the output is unchanged, and say how the count of assignments changes for $n = 50$ .

Problem 4.8.

Show that the sieve may stop its outer loop at $i = \lfloor \sqrt{n} \rfloor$ provided the surviving indices above that point are output afterwards. Which part of the proof of the theorem does this rely on?

Data Structures and Interfaces

A data structure is a way to store a non-constant amount of data, supporting a set of operations to interact with that data. The set of operations a data structure supports is its interface. Many data structures may support the same interface and differ in the cost of each operation, and many problems become easy once the data are stored in a suitable structure.

The most primitive data structure native to the Word-RAM is the static array: a contiguous sequence of words reserved in memory, supporting the static sequence interface.

StaticArray(n): allocate a new static array of size $n$ , every entry initialised to $0$ , in $\Theta(n)$ time.
get_at(i): return the word stored at index $i$ , in $\Theta(1)$ time.
set_at(i, x): write the word $x$ to index $i$ , in $\Theta(1)$ time.

The operations get_at(i) and set_at(i, x) run in constant time because every item of the array has the same size, one machine word. To store a larger object at an index, the machine word there is read as the memory address of a larger piece of memory holding the object. A Python tuple is like a static array without set_at(i, x).

Classes

Python writes a data structure as a class: a bundle of stored values, called attributes, together with the functions that act on them, called methods.

class Counter:
    def __init__(self, start):
        self.value = start

    def increment(self):
        self.value = self.value + 1

    def __len__(self):
        return self.value

c = Counter(5)
c.increment()
print(c.value, len(c))   # 6 6

Calling Counter(5) creates a new object of the class and runs __init__ on it, with self bound to the new object and start to 5; the assignment self.value = start creates the attribute value. A call c.increment() runs the method with self bound to c. A few method names are special: len(c) calls c.__len__(), and a for loop over c calls c.__iter__().

Inside a method, yield x hands x to the for loop that is running over the object, then carries on from the same point when the loop asks for the next value; yield from X hands on every value of X in turn. This is how range produces its entries one at a time. The statement raise IndexError stops the program with an error naming a bad index, and assert test stops it with an error if test is False.

A class may be built on another: class B(A): gives B every method of A, and any method B defines with the same name replaces the one from A. Inside B, super().__init__() runs the __init__ of A.

A Static Array in Python

Python has no static array, so we imitate one with a list whose length we never change.

class StaticArray:
    def __init__(self, n):
        self.data = [None] * n

    def get_at(self, i):
        if not (0 <= i < len(self.data)): raise IndexError
        return self.data[i]

    def set_at(self, i, x):
        if not (0 <= i < len(self.data)): raise IndexError
        self.data[i] = x

Birthday Matching

Given the students of a class, each with a name and a birthday, we want two students who share a birthday, or a report that there are none. The algorithm keeps a record of the students seen so far, and checks each new student against it before adding them.

Birthday Match
Input:  n students, each a pair (name, birthday).
Output: the names of two students with the same birthday, or None.

    record ≝ a static array of length n
    for k ≝ 0 to n − 1 do
        (name₁, bday₁) ≝ student k
        for i ≝ 0 to k − 1 do
            (name₂, bday₂) ≝ record[i]
            if bday₁ = bday₂ then return (name₁, name₂)
        record[k] ≝ (name₁, bday₁)
    return None

def birthday_match(students):
    # students: tuple of (name, bday) tuples
    n = len(students)                          # O(1)
    record = StaticArray(n)                    # O(n)
    for k in range(n):                         # n passes
        (name1, bday1) = students[k]           # O(1)
        for i in range(k):                     # k passes: check the record
            (name2, bday2) = record.get_at(i)  # O(1)
            if bday1 == bday2:                 # O(1)
                return (name1, name2)          # O(1)
        record.set_at(k, (name1, bday1))       # O(1)
    return None                                # O(1)

print(birthday_match((('Ada', 'Dec 10'), ('Alan', 'Jun 23'), ('Emmy', 'Mar 23'), ('Kurt', 'Jun 23'))))
# ('Kurt', 'Alan')

We assume that each name and each birthday fits into a constant number of machine words, so that one student’s information can be read and compared in constant time. This allows names and birthdays of $O(w)$ characters from a fixed alphabet, and since $w > \log_2 n$ it still allows every student’s information to be distinct.

Every line then takes constant time except three. Building record takes $\Theta(n)$ time; the outer loop makes at most $n$ passes; and the inner loop on pass $k$ runs through the $k$ entries already in the record. The running time is therefore at most

O(n) + \sum_{k=0}^{n-1} \bigl( O(1) + k \cdot O(1) \bigr) = O(n) + O(n) + O\!\left(\frac{n(n-1)}{2}\right) = O(n^2),

using the sum of an arithmetic progression. This is quadratic in $n$ . A different data structure for the record does better, and the hashing section at the end of this chapter gives one.

Problem 4.9.

Suppose birthdays are given as integers $0, \ldots, 365$ (with $365$ for 29 February). Rewrite birthday_match so that it runs in $O(n)$ time, using a static array of length $366$ indexed by birthday. Where does your running-time argument use the fact that the number of possible birthdays does not grow with $n$ ?

Sequences and Sets

We use two interfaces, which differ in what decides the order of the stored items.

Sequences maintain a collection of items in an extrinsic order: each stored item has a rank in the sequence, including a first item and a last item. Extrinsic means that the first item is first not because of what the item is, but because some external party put it there. An iterable below is anything a for loop can run over, such as a tuple, a string, a list or a range.

	Operation	Meaning
Container	`build(X)`	given an iterable `X`, build a sequence from the items of `X`
	`len()`	return the number of stored items
Static	`iter_seq()`	return the stored items one by one in sequence order
	`get_at(i)`	return the item of rank `i`
	`set_at(i, x)`	replace the item of rank `i` with `x`
Dynamic	`insert_at(i, x)`	add `x` as the item of rank `i`
	`delete_at(i)`	remove and return the item of rank `i`
	`insert_first(x)`	add `x` as the first item
	`delete_first()`	remove and return the first item
	`insert_last(x)`	add `x` as the last item
	`delete_last()`	remove and return the last item

The insert and delete operations change the rank of every item after the one inserted or deleted. Two restricted forms of a sequence have names of their own.

Definition 4.13 (Stack and queue).

A stack is a sequence used only through insert_last and delete_last: the item removed is always the one most recently added, “last in, first out”. A queue is a sequence used only through insert_last and delete_first: the item removed is always the one added longest ago, “first in, first out”.

The call stack of the functions section is a stack in this sense. With a Python list, append and pop() are insert_last and delete_last.

Sets, by contrast, maintain a collection of items based on an intrinsic property of what the items are, usually a unique key x.key attached to each item x. Sets generalise dictionaries and other databases queried by content.

	Operation	Meaning
Container	`build(X)`	given an iterable `X`, build a set from the items of `X`
	`len()`	return the number of stored items
Static	`find(k)`	return the stored item with key `k`
Dynamic	`insert(x)`	add `x` to the set, replacing the item with key `x.key` if there is one
	`delete(k)`	remove and return the stored item with key `k`
Order	`iter_ord()`	return the stored items one by one in key order
	`find_min()`	return the stored item with smallest key
	`find_max()`	return the stored item with largest key
	`find_next(k)`	return the stored item with smallest key larger than `k`
	`find_prev(k)`	return the stored item with largest key smaller than `k`

The find operations return None if no qualifying item exists. In Python an item with a key can be an object of a small class:

class Item:
    def __init__(self, key, value):
        self.key = key
        self.value = value

We now give three data structures for the sequence interface. None of them supports insertion or deletion at an arbitrary rank in less than linear time.

Array Sequences

Computer memory is a finite resource. On a modern computer many running programs share the same main memory, so the operating system assigns a fixed range of memory addresses to each of them. When a program asks to store a variable it must say how much memory, how many bits, the variable needs; the operating system finds that much free memory in the program’s assigned range and reserves it, or allocates it, until it is no longer needed. Python hides memory management from the programmer, but whenever Python is asked to store something it makes such a request, for a fixed amount of memory, behind the scenes.

Now suppose a program wants to store two arrays, each of ten $64$ -bit words. It makes two requests, for $640$ bits each, and the operating system might reserve the first ten words of the program’s range for the first array $A$ and the next ten for the second array $B$ . Later an eleventh word $w$ has to be added to $A$ , and there is no room next to $A$ : the start of the range is to its left, and $B$ is to its right. One could shift $B$ right to make room, but much other data may already be reserved beyond $B$ and would have to move too. It is better to request eleven new words, copy $A$ into the start of the new allocation, store $w$ at the end, and release the old ten words for later requests.

Memory itself is one large fixed-length array, from which the operating system allocates. Implementing a sequence with an array, so that index $i$ of the array holds the item of rank $i$ , makes get_at and set_at take $O(1)$ time by random access. Inserting or deleting, however, means moving items and resizing the array, and these operations take linear time in the worst case.

class Array_Seq:
    def __init__(self):                     # O(1)
        self.A = []
        self.size = 0

    def __len__(self): return self.size     # O(1)
    def __iter__(self): yield from self.A   # O(n) iter_seq

    def build(self, X):                     # O(n)
        self.A = [a for a in X]             # stands in for a static array
        self.size = len(self.A)

    def get_at(self, i): return self.A[i]   # O(1)
    def set_at(self, i, x): self.A[i] = x   # O(1)

    def _copy_forward(self, i, n, A, j):    # O(n)
        for k in range(n):
            A[j + k] = self.A[i + k]

    def _copy_backward(self, i, n, A, j):   # O(n)
        for k in range(n - 1, -1, -1):
            A[j + k] = self.A[i + k]

    def insert_at(self, i, x):              # O(n)
        n = len(self)
        A = [None] * (n + 1)
        self._copy_forward(0, i, A, 0)
        A[i] = x
        self._copy_forward(i, n - i, A, i + 1)
        self.build(A)

    def delete_at(self, i):                 # O(n)
        n = len(self)
        A = [None] * (n - 1)
        self._copy_forward(0, i, A, 0)
        x = self.A[i]
        self._copy_forward(i + 1, n - i - 1, A, i)
        self.build(A)
        return x

    def insert_first(self, x): self.insert_at(0, x)             # O(n)
    def delete_first(self): return self.delete_at(0)            # O(n)
    def insert_last(self, x): self.insert_at(len(self), x)      # O(n)
    def delete_last(self): return self.delete_at(len(self) - 1) # O(n)

_copy_forward(i, n, A, j) copies the $n$ items starting at index $i$ into the array A starting at index $j$ , from left to right; _copy_backward copies the same items from right to left, which matters when source and destination overlap. A method name starting with an underscore is a convention for “used only inside the class”.

In a sorted array, whose items are arranged in the order of their keys, an item can be found far faster than by scanning, by the bisection of the last lesson; binary search in the next lesson makes this precise. Inserting an object while preserving the order is then harder, and costs $O(n)$ time. Deleting an element, even when its index is known, also costs $O(n)$ time if the array is to have no gaps and keep the order of the remaining elements.

Problem 4.10.

Trace Array_Seq on build((5, 7, 9)), then insert_at(1, 6), then delete_at(0), giving the list self.A after each operation. Count the item copies each of the two dynamic operations makes, and give that count for insert_at(i, x) on a sequence of length $n$ .

Linked Lists

In a linked list, inserting or deleting an item does not move the others. Its items are kept in a certain order, as in an array, but they can be stored anywhere in memory, in places independent of one another. With each item we store a reference to the place of the next item, its successor; for the last item this reference is None, which marks the end of the list. One further reference to the first item, the head, is needed to reach the list at all.

Linked lists can be singly or doubly linked. In a doubly linked list each item also stores a reference to its predecessor, and the list keeps a reference to its last item, the tail. This allows an item whose place is known to be deleted with a number of steps bounded by a constant independent of the length of the list: the running time is $O(1)$ .

Figure 4.1. A doubly linked list with three items. Every item holds a data entry, a reference to the previous item and a reference to the next; a small open circle is None. The names first and last refer to the two ends. Deleting the accented parts leaves a singly linked list.

The Python below is a singly linked list. A node holds an item and a reference next; later_node(i) walks $i$ steps along the list.

class Linked_List_Node:
    def __init__(self, x):                  # O(1)
        self.item = x
        self.next = None

    def later_node(self, i):                # O(i)
        if i == 0: return self
        assert self.next
        return self.next.later_node(i - 1)

class Linked_List_Seq:
    def __init__(self):                     # O(1)
        self.head = None
        self.size = 0

    def __len__(self): return self.size     # O(1)

    def __iter__(self):                     # O(n) iter_seq
        node = self.head
        while node:
            yield node.item
            node = node.next

    def build(self, X):                     # O(n)
        for a in reversed(X):
            self.insert_first(a)

    def get_at(self, i):                    # O(i)
        node = self.head.later_node(i)
        return node.item

    def set_at(self, i, x):                 # O(i)
        node = self.head.later_node(i)
        node.item = x

    def insert_first(self, x):              # O(1)
        new_node = Linked_List_Node(x)
        new_node.next = self.head
        self.head = new_node
        self.size += 1

    def delete_first(self):                 # O(1)
        x = self.head.item
        self.head = self.head.next
        self.size -= 1
        return x

    def insert_at(self, i, x):              # O(i)
        if i == 0:
            self.insert_first(x)
            return
        new_node = Linked_List_Node(x)
        node = self.head.later_node(i - 1)
        new_node.next = node.next
        node.next = new_node
        self.size += 1

    def delete_at(self, i):                 # O(i)
        if i == 0:
            return self.delete_first()
        node = self.head.later_node(i - 1)
        x = node.next.item
        node.next = node.next.next
        self.size -= 1
        return x

    def insert_last(self, x): self.insert_at(len(self), x)       # O(n)
    def delete_last(self): return self.delete_at(len(self) - 1)  # O(n)

reversed(X) runs through X from its last entry to its first, so that inserting each at the front leaves them in their original order; a test while node: holds as long as node is not None.

Linked lists have a disadvantage: bisection cannot be applied to them, since reaching the middle item means walking to it. Scanning a linked list is also slower than scanning an array, by a constant factor only, because today’s computers reach consecutive storage places substantially faster than places far apart.

Problem 4.11.

Add a method reverse() to Linked_List_Seq that reverses the order of the items in $O(n)$ time and $O(1)$ auxiliary space, by changing the next references rather than the items. State the invariant your loop maintains.

Dynamic Arrays

The array sequence’s dynamic operations take time linear in the length of the array. One way to add items without paying a linear transfer cost every time is to over-allocate: request more space than the array currently needs, so that inserting an item means writing it into the next empty slot. This trades a little extra space for constant-time insertion. Any extra allocation is bounded, however; repeated insertions eventually fill it, and the array must be reallocated and copied again. Extra space reserved also means less space for the rest of the program.

Python does not append to the end of a list in worst-case $O(1)$ time. Sometimes appending to a Python list requires $O(n)$ time to transfer the array to a larger allocation, so sometimes appending takes linear time. Allocating extra space in the right way guarantees that any sequence of $n$ insertions takes $O(n)$ time in total, because the linear-time transfers happen rarely, so insertion takes $O(1)$ time per insertion on average over the sequence.

Definition 4.14 (Amortized cost).

An operation has amortized cost $T(n)$ if every sequence of $k$ operations, starting from an empty data structure, takes at most $k \cdot T(n)$ time in total, where $n$ is the largest size the structure reaches.

The cost of an expensive operation is amortized, that is spread, across the many cheap ones. To achieve amortized constant-time insertion at the end of an array, the strategy is to allocate extra space in proportion to the size of the array stored. Allocating $\Theta(n)$ extra space ensures that a linear number of insertions must occur before an insertion overflows the allocation. A typical implementation allocates double the space needed for the current array, which is called table doubling; any constant fraction of extra space achieves the same bound. The list implementation of CPython, the standard Python interpreter, has used the rule

new_allocated = newsize // 8 + (3 if newsize < 9 else 6)   # extra slots

when a list must grow to newsize items, translated here from C; recent versions use a rule of the same shape. The extra allocation is modest, about one eighth of the size of the array, but it is still linear in that size, so on average $n/8$ insertions are performed for every linear-time reallocation: amortized constant time.

Now consider removing items from the end. Popping the last item can be done in constant time by decrementing a stored length, which Python does. But if many items are removed from a large list, the unused allocation can hold a large amount of memory that is not available for other purposes. Once the array is small enough we transfer its contents to a smaller allocation and release the larger one. The new allocation cannot be exactly the size of the array, since an immediate insertion would then trigger another reallocation. For constant amortized time over any sequence of appends and pops, there must remain a linear fraction of unused space whenever we rebuild into a smaller array, which guarantees that $\Omega(n)$ further operations must occur before the next reallocation.

The implementation below does both with table-doubling proportions. When an append would pass the end of the allocation, the contents move to an allocation twice as large. When removals bring the array down to a quarter of its allocation, the contents move to an allocation half as large. Python lists already work this way; the code shows how amortized constant-time append and pop can be implemented.

class Dynamic_Array_Seq(Array_Seq):
    def __init__(self, r = 2):              # O(1)
        super().__init__()
        self.size = 0
        self.r = r
        self._compute_bounds()
        self._resize(0)

    def __len__(self): return self.size     # O(1)

    def __iter__(self):                     # O(n)
        for i in range(len(self)): yield self.A[i]

    def build(self, X):                     # O(n)
        for a in X: self.insert_last(a)

    def _compute_bounds(self):              # O(1)
        self.upper = len(self.A)
        self.lower = len(self.A) // (self.r * self.r)

    def _resize(self, n):                   # O(1) or O(n)
        if (self.lower < n < self.upper): return
        m = max(n, 1) * self.r
        A = [None] * m
        self._copy_forward(0, self.size, A, 0)
        self.A = A
        self._compute_bounds()

    def insert_last(self, x):               # O(1) amortized
        self._resize(self.size + 1)
        self.A[self.size] = x
        self.size += 1

    def delete_last(self):                  # O(1) amortized
        self.A[self.size - 1] = None
        self.size -= 1
        self._resize(self.size)

    def insert_at(self, i, x):              # O(n)
        self.insert_last(None)
        self._copy_backward(i, self.size - (i + 1), self.A, i + 1)
        self.A[i] = x

    def delete_at(self, i):                 # O(n)
        x = self.A[i]
        self._copy_forward(i + 1, self.size - (i + 1), self.A, i)
        self.delete_last()
        return x

    def insert_first(self, x): self.insert_at(0, x)       # O(n)
    def delete_first(self): return self.delete_at(0)      # O(n)

def __init__(self, r = 2) gives the parameter r a default value: Dynamic_Array_Seq() uses r = 2, and Dynamic_Array_Seq(3) uses r = 3. The class inherits get_at, set_at and the two copying methods from Array_Seq.

Proposition 4.15 (Appending is amortized constant time).

Starting from an empty Dynamic_Array_Seq with $r = 2$ , any sequence of $n$ calls of insert_last takes $O(n)$ time in total.

Discussion.

Each call does a constant amount of work apart from reallocations, so we bound the total cost of the reallocations. A reallocation at size $s$ allocates about $2s$ slots and copies $s$ items, so it costs $O(s)$ . The sizes at which reallocations happen are the points where the allocation fills up, and because the allocation doubles each time these sizes grow geometrically. Their sum is therefore dominated by the last one, which is less than $n$ , and a geometric sum bounds the total by a constant times $n$ .

Proof.

Without removals lower never exceeds a quarter of the allocation, so _resize(s + 1) reallocates exactly when $s + 1$ reaches the current allocation upper. The initial call _resize(0) allocates $2$ slots. After a reallocation triggered at size $s + 1 = m$ the allocation becomes $2m$ . So the allocations are $2, 4, 8, \ldots$ , and the insertions that reallocate are those that bring the size to $2, 4, 8, \ldots$ ; the one bringing the size to $2^t$ copies $2^t - 1$ items and allocates $2^{t+1}$ slots, at cost at most $C\,2^{t+1}$ for a constant $C$ .

Over $n$ insertions these are the $t$ with $2^t \leqslant n$ , that is $1 \leqslant t \leqslant m$ with $m = \lfloor \log_2 n \rfloor$ . Their total cost is at most

\sum_{t=1}^{m} C\, 2^{t+1} = 4C\,(2^m - 1) < 4C\,n

by the geometric sum. Every other part of every call costs $O(1)$ , contributing $O(n)$ . The total is $O(n)$ .

The worst-case costs of the three sequence structures are collected below, with (a) marking an amortized bound.

Data structure	`build(X)`	`get_at(i)`, `set_at(i, x)`	`insert_first(x)`, `delete_first()`	`insert_last(x)`, `delete_last()`	`insert_at(i, x)`, `delete_at(i)`
Array	$n$	$1$	$n$	$n$	$n$
Linked list	$n$	$n$	$1$	$n$	$n$
Dynamic array	$n$	$1$	$n$	$1$ (a)	$n$

Each entry is the $O(\cdot)$ bound as a function of the number $n$ of stored items.

Problem 4.12.

Take $r = 2$ and start from an empty Dynamic_Array_Seq. Show that any sequence of $n$ operations, each an insert_last or a delete_last on a nonempty array, takes $O(n)$ time in total. Then show that if the array were halved as soon as it fell to half full, rather than a quarter, some sequence of $n$ operations would take $\Theta(n^2)$ time.

Problem 4.13.

Extend Linked_List_Seq with a reference to its last node so that insert_last takes $O(1)$ time, and extend Dynamic_Array_Seq so that insert_first and delete_first take $O(1)$ amortized time. Which operation cannot be made $O(1)$ in a singly linked list with a tail reference, and why?

Hashing

The set interface asks for find(k). Stored in an array in no particular order, a set answers find(k) by scanning, in $O(n)$ time. With comparisons alone we cannot do much better: the lower bound for searching in the next lesson shows that $\Omega(\log n)$ comparisons are needed for a search among $n$ items. Reading memory at an address computed from the key is not a comparison, and it reaches any memory cell in one step. Hashing uses this.

Direct Access Arrays

A direct access array is a static array with a meaning attached to each index: an item $x$ with key $k$ is stored at index $k$ . This makes sense only when keys are integers. Anything stored in a computer can be associated with an integer, for example its sequence of bits read as a binary number, or its address in memory, so from now on keys are integers.

Suppose we want to store a set of $n$ items whose unique integer keys lie in the range $0, \ldots, u - 1$ . We store them in a direct access array of length $u$ , whose slot $i$ holds the item with key $i$ if there is one. To find the item with key $i$ , look in slot $i$ : worst-case constant time. The order operations are slow: the first, last or next item could be in any slot, so they may take $u$ time.

class DirectAccessArray:
    def __init__(self, u): self.A = [None] * u   # O(u)
    def find(self, k): return self.A[k]          # O(1)
    def insert(self, x): self.A[x.key] = x       # O(1)
    def delete(self, k): self.A[k] = None        # O(1)

    def find_next(self, k):                      # O(u)
        for i in range(k + 1, len(self.A)):
            if self.A[i] is not None:
                return self.A[i]

    def find_max(self):                          # O(u)
        for i in range(len(self.A) - 1, -1, -1):
            if self.A[i] is not None:
                return self.A[i]

    def delete_max(self):                        # O(u)
        for i in range(len(self.A) - 1, -1, -1):
            x = self.A[i]
            if x is not None:
                self.A[i] = None
                return x

A direct access array needs a slot for every possible key in the range. When $u$ is very large compared with the number of items stored, the array is wasteful, or impossible to store at all. Suppose we wanted find(k) on ten-letter names with a direct access array. There are $u = 26^{10} \approx 1.4 \times 10^{14}$ possible names, and even an array of one bit per name would need $17.6$ terabytes.

The following counting principle is used below to show that collisions cannot be avoided.

Proposition 4.16 (The pigeonhole principle).

If $N$ objects are placed in $r$ boxes, some box contains at least $\lceil N/r \rceil$ objects.

Discussion.

The argument is by contradiction on the total. If every box held fewer than $\lceil N/r \rceil$ objects, each would hold at most $\lceil N/r \rceil - 1$ , and the $r$ boxes together would hold fewer than $N$ . It remains to check the arithmetic step that $\lceil N/r \rceil - 1 < N/r$ , which is the defining property of the ceiling.

Proof.

Suppose every box contains at most $\lceil N/r \rceil - 1$ objects. By the definition of the ceiling, $\lceil N/r \rceil - 1 < N/r$ , so the total number of objects is at most $r\bigl(\lceil N/r \rceil - 1\bigr) < r \cdot N/r = N$ , a contradiction.

Hash Functions

To keep fast search while using only $O(n)$ space when $n$ is much smaller than $u$ , we store the items in a smaller direct access array of $m = O(n)$ slots, growing and shrinking it like a dynamic array according to the number of items stored. This needs a way to send each key to one of the $m$ slots.

Definition 4.17 (Hash function and hash table).

A hash function is a function

h : \{0, \ldots, u - 1\} \to \{0, \ldots, m - 1\} ,

and $h(k)$ is the hash of the key $k$ . The smaller direct access array of $m$ slots in which an item with key $k$ is stored at slot $h(k)$ is a hash table. Two keys $k_1 \neq k_2$ collide if $h(k_1) = h(k_2)$ .

If $h$ happens to be injective on the $n$ keys being stored, so that no two of them collide, the hash table acts as a direct access array over the smaller range $\{0, \ldots, m-1\}$ and supports worst-case constant-time search. When $m < u$ , however, the pigeonhole principle puts at least two of the $u$ possible keys in some slot, and when the keys to be stored are not known in advance it is very unlikely that a chosen hash function avoids collisions among them. (If all the keys are known in advance, a scheme called perfect hashing can be designed to avoid collisions between them.)

A slot can hold one item, so colliding items must be stored somewhere. Either they are stored elsewhere in the same array, which is called open addressing and is how most hash tables are implemented in practice, though it is harder to analyse; or they are stored in a separate structure, which is called chaining and is the strategy we adopt.

Chaining

In chaining each slot of the hash table holds a reference to a chain, a separate data structure supporting the dynamic set operations find(k), insert(x) and delete(k). A chain is usually a linked list or a dynamic array, and any implementation will do provided each operation takes at most linear time in the length of the chain. To insert an item $x$ , insert it into the chain at slot $h(x.\mathrm{key})$ ; to find or delete a key $k$ , find or delete it in the chain at slot $h(k)$ .

Figure 4.2. Chaining with

m = 5

slots and

h(k) = k \bmod 5

. The keys

12

and

47

collide in slot

2

, and

8

23

and

63

in slot

3

; each slot refers to a chain holding the items that hash to it.

A chain in Python can be a list of items searched from the front:

class Chain:
    def __init__(self): self.items = []          # O(1)
    def __iter__(self): yield from self.items    # O(length)

    def find(self, k):                           # O(length)
        for x in self.items:
            if x.key == k: return x
        return None

    def insert(self, x):                         # O(length)
        for i in range(len(self.items)):
            if self.items[i].key == x.key:
                self.items[i] = x                # replace, nothing added
                return False
        self.items.append(x)
        return True

    def delete(self, k):                         # O(length)
        for i in range(len(self.items)):
            if self.items[i].key == k:
                return self.items.pop(i)
        return None

We want chains to be short: if every chain holds a constant number of items, the dynamic set operations run in constant time. If instead the hash function sends every stored key to the same slot, one chain has linear length and the operations can take linear time. A good hash function keeps collisions rare, so that no chain grows long.

Choosing a Hash Function

The simplest map from keys in $\{0, \ldots, u-1\}$ to $\{0, \ldots, m-1\}$ is the division method: $h(k) = k \bmod m$ , in Python k % m. If the keys stored are spread evenly over the range, it spreads them roughly evenly among the slots and the chains stay short. But if all of them happen to leave the same remainder on division by $m$ , every one lands in one chain. We want performance that does not depend on which keys are stored, and no single hash function gives that.

Remark (Every fixed hash function has bad inputs).

If $u > nm$ , then every hash function $h$ from $\{0, \ldots, u-1\}$ to $\{0, \ldots, m-1\}$ sends some $n$ keys to the same slot. By the pigeonhole principle some slot receives at least $\lceil u/m \rceil$ keys, and $u/m > n$ .

Instead we choose the hash function at random, from a large family, after the keys are fixed. Then no set of keys is bad for most of the family, and we can bound the cost on average over the choice of function. The averages we need are over a finite set of equally likely choices.

Definition 4.18 (Uniform choice from a finite family).

Let $\mathcal{H}$ be a finite nonempty set, and let $h$ be chosen from $\mathcal{H}$ with every member equally likely. For a property $P$ of members of $\mathcal{H}$ , and a function $X : \mathcal{H} \to \mathbb{R}$ , the probability of $P$ and the expectation of $X$ are

\Pr_{h \in \mathcal{H}}\bigl[P(h)\bigr] = \frac{\#\{h \in \mathcal{H} : P(h)\}}{\#\mathcal{H}}, \qquad \mathbb{E}_{h \in \mathcal{H}}\bigl[X(h)\bigr] = \frac{1}{\#\mathcal{H}} \sum_{h \in \mathcal{H}} X(h) .

Two facts follow from the laws of summation. Expectation is linear: $\mathbb{E}[X + Y] = \mathbb{E}[X] + \mathbb{E}[Y]$ and $\mathbb{E}[cX] = c\,\mathbb{E}[X]$ , because the sum defining the left side splits into the sums defining the right. And the expectation of an Iverson bracket is a probability: $\mathbb{E}\bigl[[P(h)]\bigr] = \Pr[P(h)]$ , since the bracket contributes $1$ for each $h$ with $P(h)$ and $0$ otherwise. The expectation here is over the choice of hash function, which is made independently of the input. It is not an average over possible input keys.

Definition 4.19 (Universal family).

A finite family $\mathcal{H}$ of hash functions from $\{0, \ldots, u-1\}$ to $\{0, \ldots, m-1\}$ is universal if for any two keys $k_i \neq k_j$ in $\{0, \ldots, u-1\}$ ,

\Pr_{h \in \mathcal{H}}\bigl[h(k_i) = h(k_j)\bigr] \leqslant \frac{1}{m} .

A family that performs well is

\mathcal{H}(m, p) = \bigl\{\, h_{ab}(k) = \bigl((ak + b) \bmod p\bigr) \bmod m \;\bigm|\; a, b \in \{0, \ldots, p-1\},\ a \neq 0 \,\bigr\},

where $p$ is a prime larger than $u$ . A single function of the family is specified by choosing concrete values of $a$ and $b$ . This family is universal. The proof uses arithmetic modulo a prime, which these notes have not developed, and we take it as given.

Proposition 4.20 (Expected chain length).

Let $\mathcal{H}$ be a universal family, and let $n$ distinct keys $k_0, \ldots, k_{n-1}$ be stored in a hash table of $m$ slots with chaining, using $h$ chosen uniformly from $\mathcal{H}$ . For each $i$ , the expected number of stored keys in the chain at slot $h(k_i)$ is at most $1 + (n-1)/m$ .

Discussion.

The chain holding $k_i$ contains exactly the stored keys that collide with $k_i$ , together with $k_i$ itself. So its length is a sum of Iverson brackets, one for each stored key, and linearity turns the expectation of the sum into a sum of expectations. Each bracket’s expectation is a collision probability: the one for $j = i$ is $1$ , and each of the $n - 1$ others is at most $1/m$ by universality.

Proof.

For each $j$ let $X_{ij}(h) = [\,h(k_i) = h(k_j)\,]$ , which is $1$ if $k_i$ and $k_j$ collide under $h$ and $0$ otherwise. The number of stored keys in the chain at slot $h(k_i)$ is $X_i = \sum_{j} X_{ij}$ , and $X_{ii} = 1$ for every $h$ . By linearity and universality,

\mathbb{E}_{h \in \mathcal{H}}[X_i] = \sum_{j} \mathbb{E}[X_{ij}] = 1 + \sum_{j \neq i} \Pr_{h \in \mathcal{H}}\bigl[h(k_i) = h(k_j)\bigr] \leqslant 1 + \sum_{j \neq i} \frac{1}{m} = 1 + \frac{n-1}{m} .

If the table is at least linear in the number of items stored, $m = \Omega(n)$ , the expected length of any chain is $1 + (n-1)/\Omega(n) = O(1)$ . A hash table with chaining and a hash function chosen at random from a universal family therefore performs the dynamic set operations in expected constant time, the expectation being over the choice of hash function and not over the input keys. To keep $m = \Theta(n)$ , insertions and deletions may have to rebuild the table at a different size and reinsert every item, as a dynamic array does; this makes the bounds for the dynamic operations amortized as well.

A Hash Table in Python

The statement from random import randint makes the function randint available: randint(a, b) returns an integer chosen uniformly from $a, a+1, \ldots, b$ . The keys are assumed to be integers below the prime $p = 2^{31} - 1$ . In [Chain() for _ in range(m)] the name _ is the usual name for a loop variable whose value is not used.

from random import randint

class Hash_Table_Set:
    def __init__(self):                          # O(1)
        self.A = []
        self.size = 0
        self.p = 2**31 - 1                       # a prime larger than every key
        self.a = randint(1, self.p - 1)
        self.b = randint(0, self.p - 1)
        self._compute_bounds()
        self._resize(0)

    def __len__(self): return self.size          # O(1)

    def __iter__(self):                          # O(n)
        for chain in self.A:
            yield from chain

    def build(self, X):                          # O(n) expected
        for x in X: self.insert(x)

    def _hash(self, k, m):                       # O(1)
        return ((self.a * k + self.b) % self.p) % m

    def _compute_bounds(self):                   # O(1)
        self.upper = len(self.A)
        self.lower = len(self.A) // 4

    def _resize(self, n):                        # O(n)
        if self.lower < n < self.upper: return
        m = max(n, 1) * 2
        A = [Chain() for _ in range(m)]
        for x in self:
            A[self._hash(x.key, m)].insert(x)
        self.A = A
        self._compute_bounds()

    def find(self, k):                           # O(1) expected
        h = self._hash(k, len(self.A))
        return self.A[h].find(k)

    def insert(self, x):                         # O(1) amortized expected
        self._resize(self.size + 1)
        h = self._hash(x.key, len(self.A))
        added = self.A[h].insert(x)
        if added: self.size += 1
        return added

    def delete(self, k):                         # O(1) amortized expected
        assert len(self) > 0
        h = self._hash(k, len(self.A))
        x = self.A[h].delete(k)
        if x is not None:
            self.size -= 1
            self._resize(self.size)
        return x

    def find_min(self):                          # O(n)
        out = None
        for x in self:
            if (out is None) or (x.key < out.key):
                out = x
        return out

    def find_max(self):                          # O(n)
        out = None
        for x in self:
            if (out is None) or (x.key > out.key):
                out = x
        return out

    def find_next(self, k):                      # O(n)
        out = None
        for x in self:
            if x.key > k:
                if (out is None) or (x.key < out.key):
                    out = x
        return out

    def find_prev(self, k):                      # O(n)
        out = None
        for x in self:
            if x.key < k:
                if (out is None) or (x.key > out.key):
                    out = x
        return out

    def iter_ord(self):                          # O(n^2)
        x = self.find_min()
        while x:
            yield x
            x = self.find_next(x.key)

The number of items stays strictly between a quarter of the number of slots and the number of slots; when it leaves that range the table is rebuilt with twice as many slots as items, which is the rule of Dynamic_Array_Seq with $r = 2$ . So $m = \Theta(n)$ throughout, and by the proposition every chain has expected constant length.

Problem 4.14.

Insert the keys $3, 13, 23, 33, 8, 18$ in that order into a hash table of $m = 10$ slots with chaining and the division method $h(k) = k \bmod 10$ , and draw the table. Then do the same with $m = 7$ . Describe every set of keys that makes the division method with $m = 10$ put all keys into one chain.

Problem 4.15.

Rewrite birthday_match using a Hash_Table_Set keyed by birthday, with birthdays given as integers, so that it runs in expected $O(n)$ time. Explain why the $O(n)$ bound is an expectation and what it is taken over.

Graphs

A graph records which pairs of objects are related: towns joined by roads, people who know each other, states of a computation that lead to one another. The objects are the vertices and the related pairs are the edges.

Undirected Graphs

Definition 4.21 (Undirected graph).

An undirected graph is a pair $G = (S, A)$ , where $S$ is a finite set of vertices and $A$ is a set of unordered pairs $\{s_i, s_j\}$ of vertices. Such a pair is an edge. Unless stated otherwise, the two vertices of an edge are distinct.

The vertices $s_i, s_j$ joined by an edge are adjacent, and we write

\operatorname{Adj}(s_i) = \bigl\{\, s_j \in S : \{s_i, s_j\} \in A \,\bigr\}

for the set of vertices adjacent to $s_i$ . We draw an edge as a line between its endpoints.

Figure 4.3. A graph with

S = \{1, \ldots, 6\}

and four edges. Vertex

4

lies on no edge.

Here $S = \{1, 2, 3, 4, 5, 6\}$ and $A = \bigl\{\{1, 2\}, \{1, 5\}, \{2, 5\}, \{3, 6\}\bigr\}$ . Vertex $4$ is isolated: it belongs to $S$ but to no edge. For example, $\operatorname{Adj}(2) = \{1, 5\}$ and $\operatorname{Adj}(4) = \varnothing$ .

Definition 4.22 (Loops, simple graphs and multigraphs).

A loop joins a vertex to itself. A graph is simple if it has no loops and at most one edge between any two vertices. If repeated edges are allowed, the edge collection is a multiset and the graph is a multigraph. We normally work with simple graphs.

Definition 4.23 (Order and size).

The order of a graph is its number $|S|$ of vertices. Its size is its number $|A|$ of edges, counted with multiplicity for a multigraph.

The graph of Figure 4.3 has order $6$ and size $4$ , even though one vertex is isolated. The pair $\{1, 5\}$ is the same unordered edge as $\{5, 1\}$ ; listing both would not add an edge to a simple graph.

Running times of graph algorithms are functions of the graph, not of a single number, and the notation of the last chapter is extended to cover them. For a graph $G$ we write $S(G)$ and $A(G)$ for its vertex set and edge set.

Definition 4.24 (Landau notation on graphs).

Let $\mathcal{G}$ be the set of all graphs, and let $f, g : \mathcal{G} \to \mathbb{R}_{\geqslant 0}$ . We say that $f = O(g)$ if there exist $\alpha > 0$ and $n_0 \in \mathbb{N}$ such that

f(G) \leqslant \alpha \cdot g(G) \qquad \text{for all } G \in \mathcal{G} \text{ with } |S(G)| + |A(G)| \geqslant n_0 .

The notations $\Omega$ and $\Theta$ are extended in the same way.

In other words, if $f$ is greater than $g$ , then by at most a constant factor, with exceptions allowed only among graphs with fewer than $n_0$ vertices and edges together. The same definition can be made on any countable set of inputs, with a measure of size in place of $|S(G)| + |A(G)|$ . The function $f$ usually describes the running time of an algorithm or some memory requirement, and $g$ often depends only on the numbers of vertices and edges, which we write $n = |S(G)|$ and $m = |A(G)|$ throughout. Thus $O(n + m)$ means at most a constant times the number of vertices plus edges.

Directed Graphs

Definition 4.25 (Directed graph).

A directed graph is a pair $G = (S, A)$ with finite vertex set $S$ and arc set $A \subseteq S \times S$ . An arc $(s_i, s_j)$ starts at $s_i$ and ends at $s_j$ , and is drawn $s_i \to s_j$ . The vertex $s_j$ is a successor of $s_i$ , and $s_i$ a predecessor of $s_j$ .

We write

\operatorname{Succ}(s_i) = \{\, s_j : (s_i, s_j) \in A \,\}, \qquad \operatorname{Pred}(s_i) = \{\, s_j : (s_j, s_i) \in A \,\}.

Figure 4.4. A directed graph. The two curved arcs between

4

and

5

point in opposite directions, and

4

carries a loop.

In Figure 4.4,

A = \{(1, 2), (2, 4), (2, 5), (4, 1), (4, 4), (4, 5), (5, 4), (6, 3)\},

so for example $\operatorname{Succ}(4) = \{1, 4, 5\}$ and $\operatorname{Pred}(4) = \{2, 4, 5\}$ .

Definition 4.26 (Directed loops and $p$ -graphs).

A directed loop is an arc $(v, v)$ . A directed graph without loops is sometimes called elementary. A directed $p$ -graph permits at most $p$ parallel arcs with any given ordered endpoints; in a $1$ -graph the arcs form a set, not a multiset.

The pair $(4, 5)$ and the pair $(5, 4)$ are different arcs, and removing one changes the graph. Reversing every arc of a drawing exchanges each successor set with the corresponding predecessor set.

Problem 4.16.

Let $S = \{1, \ldots, 12\}$ and put an arc $(a, b)$ whenever $a \neq b$ and $a$ divides $b$ . List $\operatorname{Succ}(2)$ , $\operatorname{Pred}(12)$ and every vertex with no successors, and count the arcs.

Degree

Definition 4.27 (Degree).

In an undirected graph, the degree $d(v)$ of a vertex $v$ is the number of edge-ends at $v$ , a loop counting twice. In a directed graph, the out-degree $d^+(v)$ counts the arcs beginning at $v$ , the in-degree $d^-(v)$ counts the arcs ending at $v$ , and $d(v) = d^+(v) + d^-(v)$ . A directed loop contributes one to each of $d^+(v)$ and $d^-(v)$ .

We write $\delta(v)$ for the set of edges with an end at $v$ in an undirected graph, and $\delta^+(v)$ and $\delta^-(v)$ for the sets of arcs beginning and ending at $v$ in a directed graph.

In a graph without loops $d(v) = |\delta(v)|$ , and in a directed graph $d^+(v) = |\delta^+(v)|$ and $d^-(v) = |\delta^-(v)|$ , counting parallel arcs separately. In a simple graph $d(v) = |\operatorname{Adj}(v)|$ , and in a directed $1$ -graph $d^+(v) = |\operatorname{Succ}(v)|$ and $d^-(v) = |\operatorname{Pred}(v)|$ . For multigraphs, arcs are counted with multiplicity rather than by taking the sizes of these sets.

In Figure 4.3 the degrees of the vertices $1, 2, 3, 4, 5, 6$ are $2, 2, 1, 0, 2, 1$ . Their sum is $8 = 2|A|$ . In Figure 4.4, $d^+(4) = 3$ and $d^-(4) = 3$ : the loop counts once in each.

Proposition 4.28 (Counting edge-ends).

For an undirected graph and for a directed graph respectively,

\sum_{v \in S} d(v) = 2|A|, \qquad \sum_{v \in S} d^+(v) = \sum_{v \in S} d^-(v) = |A| .

Discussion.

Both sides of each identity count the same thing in two ways. The left side of the first sums, vertex by vertex, the edge-ends at that vertex; the right side counts the same edge-ends edge by edge, and every edge has exactly two ends, a loop included. For a directed graph every arc has one tail and one head, so summing out-degrees counts each arc once by its tail, and summing in-degrees counts it once by its head.

Proof.

Count the pairs $(v, e)$ in which $v$ is an end of the edge $e$ , a loop at $v$ giving two such pairs. Grouping by $v$ gives $\sum_{v} d(v)$ , by the definition of degree. Grouping by $e$ gives $2$ for every edge, so $2|A|$ . For a directed graph, count the pairs $(v, a)$ in which the arc $a$ begins at $v$ : grouping by $v$ gives $\sum_v d^+(v)$ , and grouping by $a$ gives $1$ for every arc, so $|A|$ . Counting the pairs in which $a$ ends at $v$ gives $\sum_v d^-(v) = |A|$ in the same way.

Example 4.29 (Odd degrees and repeated degrees).

The degree sum of an undirected graph is $2m$ , an even number. A sum of integers is even exactly when it contains an even number of odd terms: each even degree contributes zero modulo $2$ , and each odd degree contributes one. Thus the number of vertices of odd degree is even.

Also, among $n \geqslant 2$ vertices of a simple graph, two have the same degree. Every degree lies in $\{0, 1, \ldots, n-1\}$ . However, degree $n - 1$ means a vertex is adjacent to every other vertex, so no vertex can have degree $0$ at the same time. At most $n - 1$ of the $n$ listed values can occur, and putting $n$ vertices into at most $n - 1$ degree classes forces two into one class by the pigeonhole principle, Proposition 4.16 .

Kinds of Graphs

We may attach numbers to edges or arcs, to express distance, cost or capacity.

Definition 4.30 (Weighted graph).

A weighted graph $G = (S, A, \nu)$ is a graph together with a function $\nu : A \to \mathbb{R}$ , the weight. An undirected weight belongs to the unordered edge $\{u, v\}$ .

Definition 4.31 (Complete graph).

A simple undirected graph is complete if every pair of distinct vertices is joined; it is written $K_n$ when it has $n$ vertices. A loop-free directed $1$ -graph is complete when both $(u, v)$ and $(v, u)$ are arcs for every $u \neq v$ .

Figure 4.5. The complete graphs

K_3

and

K_5

, with

3

and

10

edges.

To count the edges of $K_n$ , choose two distinct vertices without regard to order. There are $n$ choices for the first vertex and $n - 1$ for the second. This counts each unordered pair twice, once in each order, so $K_n$ has $n(n-1)/2$ edges. We write

\binom{n}{2} = \frac{n(n-1)}{2},

read ” $n$ choose $2$ ”, for this number of unordered pairs among $n$ objects. In the complete directed graph both directions are arcs, so it has $n(n-1)$ arcs.

Definition 4.32 (Subgraphs).

Let $G = (S, A)$ be a directed or undirected graph. For $S' \subseteq S$ , the induced subgraph $G[S']$ has vertex set $S'$ and contains all edges or arcs of $G$ whose endpoints lie in $S'$ . A subgraph $(S', A')$ may keep only some of these: $A' \subseteq A \cap (S' \times S')$ in the directed case, with the analogous rule for unordered edges. A spanning subgraph, also called a partial subgraph, keeps every vertex but possibly deletes edges.

For a simple undirected graph, the possible edges of a subgraph on $S'$ are the unordered pairs of distinct vertices of $S'$ that were already edges of $G$ . Figure 4.6 shows both operations on a four-vertex directed graph.

Figure 4.6. A directed graph

G

(left), the spanning subgraph

G'

obtained by deleting

(2, 2)

(3, 2)

and

(3, 4)

(middle), and the induced subgraph

G[\{1, 2, 4\}]

(right).

Here $G'$ is the spanning subgraph obtained by deleting $(2, 2)$ , $(3, 2)$ and $(3, 4)$ . In contrast, the induced subgraph $G[\{1, 2, 4\}]$ retains the arcs $(2, 1)$ , $(4, 1)$ , $(4, 2)$ and $(2, 2)$ : vertex $3$ disappears, while every arc of $G$ joining the remaining vertices stays. An arc between retained vertices cannot be omitted from an induced subgraph.

Definition 4.33 (Clique and independent set).

In a simple undirected graph, a clique is a vertex set $C$ for which $G[C]$ is complete, and an independent set, also called a stable set, is a vertex set $I$ for which $G[I]$ has no edges. For a loop-free directed $1$ -graph, a directed clique contains both arcs between each pair of its vertices, while a directed stable set has no arcs at all.

Figure 4.7. The accented triangle

\{1, 5, 7\}

is a clique of maximum size;

\{2, 4, 5\}

is an independent set of maximum size.

In Figure 4.7, $\{1, 5, 7\}$ is a clique of maximum size and $\{2, 4, 5\}$ is an independent set of maximum size. To test whether $\{1, 5, 7\}$ is a clique, check the three pairs $\{1, 5\}$ , $\{1, 7\}$ , $\{5, 7\}$ ; to test whether $\{2, 4, 5\}$ is independent, check that none of its three pairs is an edge. Checking a particular set requires only pairwise tests. Proving that it is of maximum size also requires ruling out every larger set, and finding maximum cliques in arbitrary graphs is much harder than checking whether a proposed set is a clique.

Definition 4.34 (Bipartite and regular graphs).

An undirected graph is bipartite if its vertices can be divided into disjoint sets $S_1, S_2$ so that every edge has one endpoint in each. It is complete bipartite, written $K_{n_1, n_2}$ , if $|S_i| = n_i$ and every pair with one vertex in each set is an edge. A graph is $k$ -regular if every vertex has degree $k$ .

Example 4.35 ( $K_{2,3}$ and the four-cycle).

In $K_{2,3}$ , each of the two vertices of $S_1$ is joined to each of the three vertices of $S_2$ , giving $2 \cdot 3 = 6$ edges. Its degrees are $3$ on $S_1$ and $2$ on $S_2$ , so it is not regular. The graph with vertices $1, 2, 3, 4$ and edges $\{1,2\}, \{2,3\}, \{3,4\}, \{4,1\}$ , the cycle on four vertices, is $2$ -regular and bipartite, with classes $\{1, 3\}$ and $\{2, 4\}$ .

In general $K_{n_1, n_2}$ has $n_1 n_2$ edges. Fix a vertex of $S_1$ ; it is joined to each of the $n_2$ vertices of $S_2$ . There are $n_1$ such vertices, and every edge has exactly one endpoint in $S_1$ , so this counts each edge exactly once.

Example 4.36 (Counting the same thing twice).

Let a bipartite graph with parts $S_1, S_2$ be $k$ -regular, where $k > 0$ , and let it have $m$ edges. Sum the degrees of the vertices in $S_1$ . Every edge has exactly one endpoint there, so this sum counts every edge once and equals $m$ . Each of the $|S_1|$ vertices has degree $k$ , so the same sum is $k|S_1|$ . Therefore $m = k|S_1|$ . Repeating the count over $S_2$ gives $m = k|S_2|$ . The two expressions for $m$ are equal, and dividing by the positive number $k$ gives $|S_1| = |S_2|$ .

Example 4.37 (A monochromatic triangle).

Colour each edge of $K_6$ red or blue. Then there is a triangle whose three edges have the same colour. Pick a vertex $x$ . Five edges leave $x$ , so by the pigeonhole principle at least $\lceil 5/2 \rceil = 3$ of them, say $xy_1, xy_2, xy_3$ , share a colour; suppose it is red. If any edge among $y_1, y_2, y_3$ is red, that edge and the two red edges to $x$ make a red triangle. If none is red, all three edges among $y_1, y_2, y_3$ are blue, making a blue triangle. These cases cover every colouring, so the argument works for all of them.

Problem 4.17.

Show that $K_5$ has a red and blue colouring of its edges with no triangle all of one colour, so that $6$ in the last example cannot be replaced by $5$ .

Problem 4.18.

Show that a graph is bipartite if it has no cycle of odd length, in the sense of the next section, by colouring each vertex according to the parity of its distance from a fixed vertex in its component. Show conversely that a bipartite graph has no cycle of odd length.

Walks, Paths, Cycles and Distance

Definition 4.38 (Walks and paths in a directed graph).

In a directed graph, a walk from $u$ to $v$ is a sequence $\langle s_0, s_1, \ldots, s_k \rangle$ of vertices with $s_0 = u$ , $s_k = v$ and $(s_{i-1}, s_i) \in A$ for every $1 \leqslant i \leqslant k$ . Its length is $k$ . The vertex $v$ is reachable from $u$ if such a walk exists. A simple path is a walk with no repeated vertex. A closed walk has $s_0 = s_k$ and $k \geqslant 1$ ; a simple directed cycle is a closed walk with no further repeated vertices. A loop is a cycle of length one.

A walk may repeat vertices; a simple path may not. We allow the walk $\langle u \rangle$ of length zero from $u$ to itself, so that every vertex is reachable from itself. This convention is used for matrix powers below. When a positive number of arcs is required we say positive-length reachability explicitly.

Figure 4.8. The accented arcs form the simple directed cycle

\langle 1, 2, 5, 4, 1 \rangle

In Figure 4.8, $\langle 1, 4, 2, 5 \rangle$ is a simple path, $\langle 3, 6, 6, 6 \rangle$ is a walk with the repeated vertex $6$ , $\langle 1, 2, 5, 4, 1 \rangle$ is a simple directed cycle, and $\langle 1, 2, 5, 4, 2, 5, 4, 1 \rangle$ is a closed walk that is not a simple cycle.

Definition 4.39 (Walks, trails and cycles in an undirected graph).

In an undirected graph, consecutive vertices of a walk are joined by an edge, and walks, length, reachability and simple paths are as in the directed case. A trail is a walk that uses no edge twice. A cycle is a closed trail of positive length; a simple cycle additionally has no repeated vertices except its first and last. A graph with no cycles is acyclic. In a simple undirected graph a simple cycle has length at least three.

Proposition 4.40 (A walk contains a simple path).

If there is a walk from $u$ to $v$ , there is a simple path from $u$ to $v$ .

Discussion.

If a walk visits some vertex twice, the part between the two visits can be cut out, leaving a shorter walk between the same endpoints. So a walk with the fewest edges can have no repeated vertex. The proof takes such a shortest walk, which exists because walk lengths are nonnegative integers and at least one walk exists.

Proof.

Among all walks from $u$ to $v$ , choose one, $\langle s_0, \ldots, s_k \rangle$ , with the fewest edges. If it repeated a vertex, say $s_i = s_j$ with $i < j$ , then $\langle s_0, \ldots, s_i, s_{j+1}, \ldots, s_k \rangle$ would be a walk from $u$ to $v$ with $k - (j - i) < k$ edges, since $(s_i, s_{j+1}) = (s_j, s_{j+1})$ is an arc, or edge, of the graph. Hence no vertex repeats.

Definition 4.41 (Distance and diameter).

The distance $d(u, v)$ is the length of a shortest walk from $u$ to $v$ , or $+\infty$ if $v$ is not reachable from $u$ . The diameter of a nonempty graph is $\max_{u, v \in S} d(u, v)$ , which may be $+\infty$ . In directed graphs, $d(u, v)$ and $d(v, u)$ may differ.

The two-argument $d(u, v)$ is a distance and the one-argument $d(v)$ a degree; the number of arguments tells them apart. A shortest walk to a different vertex is a simple path, by the proof of the last proposition, so it has at most $n - 1$ arcs.

In Figure 4.8, $d(1, 5) = 2$ via $1 \to 2 \to 5$ , and $d(5, 1) = 2$ via $5 \to 4 \to 1$ . The arc $3 \to 6$ gives $d(3, 6) = 1$ , but there is no directed route from $6$ to $3$ , so $d(6, 3) = \infty$ .

Problem 4.19.

Give the distance $d(u, v)$ for every ordered pair of vertices of Figure 4.8, as a $6 \times 6$ table, and find the diameter. Which vertices can reach every other vertex?

Representing a Graph

To run an algorithm on a graph we must store it. Let $G = (S, A)$ have its vertices numbered $1, \ldots, n$ .

Adjacency Lists

An adjacency list $T[i]$ lists the vertices $j$ for which $(i, j)$ is an arc, or $\{i, j\}$ is an edge. For an undirected edge $\{i, j\}$ with $i \neq j$ , $j$ appears in $T[i]$ and $i$ appears in $T[j]$ . The order within a list is arbitrary.

More generally, an adjacency list representation keeps for every vertex $v$ a list of all the edges incident with it, the set $\delta(v)$ ; for simple graphs a list of the adjacent vertices, as above, is often enough. For a directed graph one keeps two lists for each vertex, one of the outgoing arcs $\delta^+(v)$ and one of the incoming arcs $\delta^-(v)$ .

Example 4.42 (Adjacency lists of a directed graph).

The directed graph $G$ of Figure 4.6 has

T[1] = (), \qquad T[2] = (2, 1), \qquad T[3] = (1, 4, 3, 2), \qquad T[4] = (1, 2, 3).

Its arc set is exactly the nine ordered pairs described by these lists. The loop at $2$ contributes the entry $2$ to $T[2]$ , and the loop at $3$ contributes the entry $3$ to $T[3]$ . There are $0 + 2 + 4 + 3 = 9$ entries, hence nine arcs; counting list entries is a direct way to check the arc count.

Storage. There are $n$ list headers. The total number of entries is $m$ for a directed graph with $m$ arcs and $2m$ for an undirected graph with $m$ edges, a loop also taking two entries if loops are allowed. Thus storage is $O(n + m)$ .

Operations. Reading $T[i]$ gives the successors and the out-degree of $i$ quickly. Testing for one particular arc $(i, j)$ may require scanning $T[i]$ . Finding all predecessors of $j$ requires scanning all the lists, unless reverse lists are stored as well. Visiting all arcs takes $O(n + m)$ time, not merely $O(m)$ , when isolated vertices must also be visited.

Adjacency Lists in Two Arrays

We can store the adjacency lists one after another in a single array $\mathrm{Succ}[1..m]$ . A second array $\mathrm{Head}[1..n]$ gives the final position of each list, and $\mathrm{Head}[0] = 0$ gives the starting boundary of the first. The successors of $v$ then occupy

\mathrm{Succ}\bigl[\mathrm{Head}[v-1] + 1\bigr], \ldots, \mathrm{Succ}\bigl[\mathrm{Head}[v]\bigr],

and an empty list has equal consecutive boundaries. For the graph of the last example,

\bigl(\mathrm{Head}[1], \ldots, \mathrm{Head}[4]\bigr) = (0, 2, 6, 9), \qquad \mathrm{Succ} = (2, 1, 1, 4, 3, 2, 1, 2, 3).

The empty first list is encoded by $\mathrm{Head}[1] = 0$ ; the second list ends at position $2$ , and so on. These boundaries are cumulative counts: if $d^+(v)$ is the length of list $v$ , then $\mathrm{Head}[v] = d^+(1) + \cdots + d^+(v)$ .

To find the predecessors of $2$ , scan each list and record its owner $v$ whenever an entry equals $2$ ; the result is $2, 3, 4$ . This costs $O(n + m)$ even though only three names are recorded. The same cumulative-count idea produces all the predecessor lists in $O(n + m)$ : count how many times each vertex occurs in $\mathrm{Succ}$ , which gives the in-degrees; take cumulative sums to allocate a contiguous block to each vertex; then scan the arcs once more to fill the blocks.

Predecessor Lists
Input:  n, and the arrays Head[0..n] and Succ[1..m] of a directed graph.
Output: arrays PHead[0..n] and Pred[1..m] storing the predecessor lists
        in the same way.

    for v ≝ 1 to n do c[v] ≝ 0
    for i ≝ 1 to m do c[Succ[i]] ≝ c[Succ[i]] + 1
    PHead[0] ≝ 0
    for v ≝ 1 to n do
        PHead[v] ≝ PHead[v − 1] + c[v]
        free[v] ≝ PHead[v − 1] + 1
    for u ≝ 1 to n do
        for i ≝ Head[u − 1] + 1 to Head[u] do
            w ≝ Succ[i]
            Pred[free[w]] ≝ u
            free[w] ≝ free[w] + 1

Python numbers list positions from $0$ , so the successors of $v$ are the slice Succ[Head[v - 1]:Head[v]] and the positions of the blocks shift down by one.

def predecessor_lists(n, Head, Succ):
    count = [0] * (n + 1)
    for w in Succ:
        count[w] += 1
    PHead = [0] * (n + 1)
    free = [0] * (n + 1)
    for v in range(1, n + 1):
        PHead[v] = PHead[v - 1] + count[v]
        free[v] = PHead[v - 1]
    Pred = [None] * len(Succ)
    for u in range(1, n + 1):
        for w in Succ[Head[u - 1]:Head[u]]:
            Pred[free[w]] = u
            free[w] += 1
    return PHead, Pred

PHead, Pred = predecessor_lists(4, [0, 0, 2, 6, 9], [2, 1, 1, 4, 3, 2, 1, 2, 3])
print(PHead, Pred)           # [0, 3, 6, 8, 9] [2, 3, 4, 2, 3, 4, 3, 4, 3]
print(Pred[PHead[1]:PHead[2]])   # [2, 3, 4], the predecessors of 2

Each of the loops runs over the vertices or over the arcs once, so the running time is $O(n + m)$ .

Matrices

Definition 4.43 (Matrix).

An $r \times s$ matrix is a table of numbers with $r$ rows and $s$ columns. Its entry in row $i$ and column $j$ is written $M_{ij}$ ; rows run across and columns down. An $n \times n$ matrix is square, and the identity matrix $I_n$ is the square matrix with $1$ on its diagonal and $0$ elsewhere.

Two matrices of the same shape are added entry by entry. If $B$ is $r \times s$ and $C$ is $s \times t$ , their product $BC$ is the $r \times t$ matrix with

(BC)_{ij} = \sum_{\ell=1}^{s} B_{i\ell}\, C_{\ell j},

and the powers of a square matrix are $M^0 = I_n$ and $M^{k+1} = M^k M$ . This is a definition, not ordinary entrywise multiplication. For example,

\begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix} \begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix} = \begin{pmatrix} 1 & 2 \\ 0 & 1 \end{pmatrix},

because the top-right entry is $1 \cdot 1 + 1 \cdot 1 = 2$ . We use only this rule and ordinary arithmetic below. Computing one entry of the product of two $n \times n$ matrices takes $n$ multiplications, so the whole product takes $O(n^3)$ arithmetic operations.

Adjacency Matrices

For a directed $1$ -graph with vertices $1, \ldots, n$ , the adjacency matrix $M$ is the $n \times n$ matrix with

M_{ij} = \begin{cases} 1, & (i, j) \in A, \\ 0, & (i, j) \notin A . \end{cases}

For a simple undirected graph we put $M_{ij} = 1$ when $\{i, j\}$ is an edge. Then $M_{ij} = M_{ji}$ , so $M$ is symmetric, and one can store only the entries on and above the diagonal and recover the rest by reflection; this uses about half as many entries, but still $\Theta(n^2)$ space. For a directed multigraph one may instead put the number of parallel arcs into $M_{ij}$ .

Example 4.44 (An adjacency matrix).

The graph $G$ of Figure 4.6 has

M = \begin{pmatrix} 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 \\ 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 0 \end{pmatrix}.

The rows match the adjacency lists: the third row has four ones, one for each successor of $3$ .

A matrix stores $n^2$ entries. Testing whether an arc exists takes one entry lookup; scanning the successors of a vertex takes a row scan of $n$ entries; and scanning all arcs takes $O(n^2)$ time, however few arcs there are.

A second matrix records which vertices lie on which edges.

Definition 4.45 (Incidence matrix).

Let $G$ be a graph without loops, with vertices $1, \ldots, n$ and edges $e_1, \ldots, e_m$ . Its incidence matrix is the $n \times m$ matrix $N$ with, for an undirected graph,

N_{ij} = \begin{cases} 1, & i \text{ is an end of } e_j, \\ 0, & \text{otherwise}, \end{cases}

and for a directed graph $N_{ij} = -1$ if the arc $e_j$ begins at $i$ , $N_{ij} = 1$ if it ends at $i$ , and $N_{ij} = 0$ otherwise.

Example 4.46 (An incidence matrix).

Number the edges of the graph of Figure 4.3 as $e_1 = \{1, 2\}$ , $e_2 = \{1, 5\}$ , $e_3 = \{2, 5\}$ , $e_4 = \{3, 6\}$ . Its incidence matrix, with rows for the vertices $1, \ldots, 6$ , is

N = \begin{pmatrix} 1 & 1 & 0 & 0 \\ 1 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 \\ 0 & 1 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{pmatrix}.

Every column has exactly two ones, the two ends of its edge, and the sum of the entries of row $i$ is the degree $d(i)$ . Adding all the entries both ways is the count of edge-ends.

The memory requirements of the adjacency matrix and the incidence matrix are therefore $\Theta(n^2)$ and $\Theta(nm)$ . For graphs with $\Theta(n)$ edges, which is often the case, this is far more than required: adjacency lists need memory proportional to $n + m$ .

For most purposes an adjacency list is the preferred data structure. It allows $\delta(v)$ , or $\delta^+(v)$ and $\delta^-(v)$ , to be scanned for every vertex $v$ in time linear in their size, and its memory requirement is proportional to the number of vertices and edges, if we assume, as usual, that references, vertex numbers and edge numbers each need only a constant amount of memory. In the Word-RAM this is the assumption that one machine word holds any of them, which $w > \log_2 n$ allows for vertex numbers. Graph algorithms are therefore stated for this representation, and moving to the next edge in a list of edges, or reading an endpoint of an edge, is counted as an elementary operation. An adjacency matrix remains the better choice for a graph with very many edges, or when many single-arc tests are needed.

Proposition 4.47 (Powers of the adjacency matrix count walks).

Let $M$ be the adjacency matrix of a directed $1$ -graph, and $k \in \mathbb{N}_0$ . Then $(M^k)_{ij}$ is the number of walks of length $k$ from $i$ to $j$ .

Discussion.

The definition of the power is a recursion on $k$ , so the proof is an induction on $k$ . For the step, a walk of length $k+1$ from $i$ to $j$ is a walk of length $k$ from $i$ to some vertex $\ell$ followed by one arc from $\ell$ to $j$ , and $\ell$ , the second-to-last vertex, is determined by the walk. So the walks can be sorted by $\ell$ , and the number through $\ell$ is the number of $k$ -walks from $i$ to $\ell$ times $M_{\ell j}$ , which is $1$ or $0$ according as the last arc exists. Summing over $\ell$ is exactly the formula for the entry of $M^k M$ . Walks, not paths, are counted: vertices may repeat.

Proof.

For $k = 0$ , $I_n$ has $1$ in position $(i, i)$ and $0$ elsewhere, and there is exactly one walk of length $0$ from each vertex to itself and none to any other vertex.

Suppose the claim holds for $k$ . Every walk $\langle i = v_0, \ldots, v_k, v_{k+1} = j \rangle$ of length $k + 1$ has a unique second-to-last vertex $\ell = v_k$ , and consists of a walk of length $k$ from $i$ to $\ell$ followed by the arc $(\ell, j)$ . For fixed $\ell$ there are $(M^k)_{i\ell}$ choices of the first part, by the hypothesis, and $M_{\ell j}$ choices of the last arc, so $(M^k)_{i\ell} M_{\ell j}$ walks pass through $\ell$ last. Summing over $\ell$ ,

\#\{\text{walks of length } k+1 \text{ from } i \text{ to } j\} = \sum_{\ell=1}^{n} (M^k)_{i\ell}\, M_{\ell j} = (M^k M)_{ij} = (M^{k+1})_{ij} .

The directed graph $1 \to 2 \to 1$ has adjacency matrix $\begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}$ . Its square is $I_2$ : there is one walk of length two from each vertex back to itself, and none to the other vertex.

Reachability from Matrix Powers

To turn walk counts into yes-or-no answers, let $\operatorname{sgn}(x) = 0$ when $x = 0$ and $1$ when $x > 0$ , applied to every entry of a matrix.

Definition 4.48 (Transitive closure).

For a directed graph on $n$ vertices with adjacency matrix $M$ , the reflexive transitive closure is

R = \operatorname{sgn}\bigl(I + M + M^2 + \cdots + M^{n-1}\bigr),

and the transitive closure is

T = \operatorname{sgn}\bigl(M + M^2 + \cdots + M^{n}\bigr).

By the proposition, $R_{ij} = 1$ exactly when $j$ is reachable from $i$ , the walk of length zero included: a shortest walk to a different vertex is a simple path and uses at most $n - 1$ arcs. Likewise $T_{ij} = 1$ exactly when there is a walk of positive length from $i$ to $j$ , and $T = \operatorname{sgn}(MR)$ . The power $M^n$ matters on the diagonal, since a shortest closed walk of positive length may be a cycle of length $n$ . Thus $T_{ii}$ need not be $1$ , while $R_{ii} = 1$ always.

In the two-vertex graph $1 \to 2$ with no return arc,

M = \begin{pmatrix} 0 & 1 \\ 0 & 0 \end{pmatrix}, \qquad R = \begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix}, \qquad T = \begin{pmatrix} 0 & 1 \\ 0 & 0 \end{pmatrix},

and the difference on the diagonal is exactly the zero-length walk.

Computing $R$ from its definition takes $n - 2$ matrix products; repeated squaring needs far fewer.

Proposition 4.49 (Closure by repeated squaring).

For every $q \in \mathbb{N}$ ,

\prod_{j=0}^{q-1} \bigl(I + M^{2^j}\bigr) = I + M + M^2 + \cdots + M^{2^q - 1} .

Discussion.

Multiplying out the product, each term chooses from every factor either $I$ or $M^{2^j}$ , and the chosen powers multiply to $M$ raised to a sum of distinct powers of two. The claim is that every exponent $0, \ldots, 2^q - 1$ arises exactly once, which is the existence and uniqueness of the binary expansion of a number below $2^q$ . The proof is an induction on $q$ : multiplying the sum up to $M^{2^q - 1}$ by $I + M^{2^q}$ keeps the sum and adds a copy shifted up by $2^q$ , which fills in the exponents $2^q, \ldots, 2^{q+1} - 1$ .

Proof.

For $q = 1$ both sides are $I + M$ . Suppose the identity holds for $q$ . Since powers of $M$ commute with one another,

\prod_{j=0}^{q} \bigl(I + M^{2^j}\bigr) = \Bigl(\sum_{e=0}^{2^q - 1} M^{e}\Bigr)\bigl(I + M^{2^q}\bigr) = \sum_{e=0}^{2^q - 1} M^{e} + \sum_{e=0}^{2^q - 1} M^{e + 2^q} = \sum_{e=0}^{2^{q+1} - 1} M^{e} .

Let $q = \lceil \log_2 n \rceil$ , so that $2^q - 1 \geqslant n - 1$ . Powers beyond $M^{n-1}$ reveal no new reachable vertex, so $R = \operatorname{sgn}\bigl(\prod_{j<q}(I + M^{2^j})\bigr)$ , and we may replace every positive entry by $1$ after each product. The same result follows by working throughout with Boolean matrix addition (OR) and multiplication (AND followed by OR). For $n \geqslant 2$ there are $q - 1$ squarings to form $M^2, M^4, \ldots, M^{2^{q-1}}$ and $q - 1$ products to combine the $q$ factors: at most $2q - 2$ matrix products in total. One more multiplication by $M$ gives $T$ . For $n = 1$ , $R = I$ and no product is needed. For comparison, $M^K$ takes $K - 1$ products by repeated multiplication when $K \geqslant 1$ , and at most $\lfloor \log_2 K \rfloor + \operatorname{popcount}(K) - 1$ by squaring, where $\operatorname{popcount}(K)$ is the number of digits $1$ in the binary expansion of $K$ . These counts are of matrix products; each product of two $n \times n$ matrices takes $O(n^3)$ arithmetic operations.

Reflexive Transitive Closure
Input:  the adjacency matrix M of a directed graph on n vertices.
Output: the matrix R with R[i][j] = 1 exactly when j is reachable from i.

    R ≝ sgn(I + M);  P ≝ M;  k ≝ 2
    while k < n do
        P ≝ sgn(P · P)
        R ≝ sgn(R · (I + P))
        k ≝ 2k
    return R

At each test of the loop, $P = \operatorname{sgn}(M^{k/2})$ and $R = \operatorname{sgn}(I + M + \cdots + M^{k-1})$ , by the proposition; the loop stops once $k \geqslant n$ , when $R$ covers every power up to $M^{n-1}$ . In Python a matrix is a list of rows, each row a list, and M[i][j] is the entry in row i and column j, numbered from $0$ .

def product(X, Y):              # Boolean product, O(n^3)
    n = len(X)
    Z = [[0] * n for _ in range(n)]
    for i in range(n):
        for j in range(n):
            for l in range(n):
                if X[i][l] == 1 and Y[l][j] == 1:
                    Z[i][j] = 1
    return Z

def plus_identity(X):           # sgn(I + X)
    n = len(X)
    return [[1 if i == j else X[i][j] for j in range(n)] for i in range(n)]

def closure(M):
    n = len(M)
    R = plus_identity(M)
    P = M
    k = 2
    while k < n:
        P = product(P, P)
        R = product(R, plus_identity(P))
        k = 2 * k
    return R

M = [[0, 1, 0], [0, 0, 1], [0, 0, 0]]   # 1 -> 2 -> 3, numbered 0, 1, 2
print(closure(M))                       # [[1, 1, 1], [0, 1, 1], [0, 0, 1]]

The inner [0] * n must be built afresh for each row, which is what the comprehension does: [[0] * n] * n would make $n$ references to one and the same row.

Weight Matrices

For a weighted directed graph $G = (S, A, \nu)$ with vertices $s_1, \ldots, s_n$ , the weight matrix is

W_{ij} = \begin{cases} \nu(s_i, s_j), & (s_i, s_j) \in A, \\ +\infty, & (s_i, s_j) \notin A . \end{cases}

The value $+\infty$ means that there is no direct arc; it is a convention of computation, not an arc of the graph, and $W$ has entries in $\mathbb{R} \cup \{+\infty\}$ . A zero-weight arc is present and must not be confused with an absent arc.

Figure 4.9. A weighted directed graph. Each arc carries its weight.

The graph of Figure 4.9 has, with rows and columns in the order $A, B, C, E, F, G$ ,

W = \begin{array}{c|rrrrrr} & A & B & C & E & F & G \\ \hline A & \infty & 6 & \infty & \infty & \infty & -2 \\ B & \infty & \infty & \infty & \infty & \infty & 2 \\ C & \infty & 4 & \infty & \infty & -1 & \infty \\ E & \infty & 2 & 8 & \infty & 9 & \infty \\ F & \infty & \infty & \infty & \infty & \infty & \infty \\ G & \infty & \infty & -3 & \infty & \infty & \infty \end{array}

Reading row $E$ : the arcs $E \to B$ , $E \to C$ and $E \to F$ have weights $2$ , $8$ and $9$ . The entry $W_{EA} = \infty$ says that there is no arc $E \to A$ ; it says nothing about longer routes. For an undirected weighted graph the weight matrix is symmetric. A diagonal entry is $\infty$ unless a loop is present; a distance matrix, which puts $0$ on the diagonal, is a different object.

Problem 4.20.

For the graph of Figure 4.8, write down the adjacency lists, the arrays $\mathrm{Head}$ and $\mathrm{Succ}$ , and the adjacency matrix $M$ . Compute $M^2$ and $M^3$ , and check the entries $(M^2)_{15}$ and $(M^3)_{11}$ against walks you can list.

Problem 4.21.

In a directed graph a universal sink is a vertex of in-degree $n - 1$ and out-degree $0$ . Give an algorithm that decides whether a graph given by its adjacency matrix has a universal sink, using $O(n)$ matrix lookups.

Exercises on Data Structures

Exercise 4.1.

An increasing subarray of an array of integers is a run of consecutive entries whose values strictly increase. Write a Python function count_long_subarrays(A) which takes a tuple $A = (a_0, a_1, \ldots, a_{n-1})$ of $n > 0$ positive integers and returns the number of longest increasing subarrays of $A$ , that is, the number of increasing subarrays whose length is at least that of every other. For $A = (1, 3, 4, 2, 7, 5, 6, 9, 8)$ it should return $2$ , since the longest increasing subarrays have length three and there are two of them, $(1, 3, 4)$ and $(5, 6, 9)$ . Your function should run in $O(n)$ time.

Exercise 4.2.

Order the following functions so that if $f_a$ appears before $f_b$ then $f_a = O(f_b)$ , and indicate which pairs satisfy both $f_a = O(f_b)$ and $f_b = O(f_a)$ . Here $\log$ means $\log_2$ .

f_1 = \log(n^n), \qquad f_2 = (\log n)^n, \qquad f_3 = \log(n^{6006}), \qquad f_4 = (\log n)^{6006}, \qquad f_5 = \log\log(6006n).

Exercise 4.3.

Let $f$ and $g$ be functions $\mathbb{N} \to \mathbb{R}_{\geqslant 0}$ . Using the definition of $\Theta$ , prove that $\max\bigl(f(n), g(n)\bigr) = \Theta\bigl(f(n) + g(n)\bigr)$ .

Exercise 4.4.

A data structure $D$ supports the sequence operations D.build(X) in $O(n)$ time, and D.insert_at(i, x) and D.delete_at(i) each in $O(\log n)$ time, where $n$ is the number of items stored at the time of the operation. Using only these operations, describe algorithms for the following, each running in $O(k \log n)$ time. Recall that delete_at returns the deleted item.

reverse(D, i, k): reverse the order of the $k$ items of $D$ starting at index $i$ , that is, those at indices $i$ to $i + k - 1$ .
move(D, i, k, j): move the $k$ items of $D$ starting at index $i$ , in order, to be in front of the item at index $j$ , where $i \leqslant j < i + k$ is false.

Exercise 4.5.

Each node x of a doubly linked list keeps a reference x.prev to the node before it as well as x.next to the node after it, and the list L keeps L.head and L.tail, its first and last nodes. The list does not store its length.

Describe algorithms for insert_first(x), insert_last(x), delete_first() and delete_last(), each in $O(1)$ time.
Given two nodes x1 and x2 of a list L, with x1 before x2, describe a constant-time algorithm that removes all nodes from x1 to x2 inclusive from L and returns them as a new doubly linked list.
Given a node x of a list L1 and a second list L2, describe a constant-time algorithm that splices L2 into L1 after x, leaving L2 empty.
Implement these operations in Python, in a class built like Linked_List_Seq.

Exercise 4.6.

A student keeps $n$ pages of notes in a binder, the first at index $0$ and the last at index $n - 1$ , and has two bookmarks $A$ and $B$ . Describe a data structure supporting the following operations, where $n$ is the number of pages at the time of the operation. Assume both bookmarks are placed before any shift or move, and that $A$ is always at a lower index than $B$ . For each operation, say whether your running time is worst-case or amortized.

Operation	Effect	Time
`build(X)`	initialise with the pages of the iterable `X`	$O(\lvert X \rvert)$
`place_mark(i, m)`	place bookmark $m \in \{A, B\}$ between the pages at indices $i$ and $i+1$	$O(n)$
`read_page(i)`	return the page at index $i$	$O(1)$
`shift_mark(m, d)`	move bookmark $m$ , in front of the page at index $i$ , to be in front of the page at index $i + d$ , for $d \in \{-1, 1\}$	$O(1)$
`move_page(m)`	move the page in front of bookmark $m$ to be in front of the other bookmark	$O(1)$

Exercise 4.7.

Insert the integer keys $47, 61, 36, 52, 56, 33, 92$ in this order into a hash table of size $7$ using the hash function $h(k) = (10k + 4) \bmod 7$ . Each slot stores a linked list of the keys hashing to it, later insertions being appended at the end. Draw the table after all keys have been inserted.
Suppose instead $h(k) = \bigl((10k + 4) \bmod c\bigr) \bmod 7$ for a positive integer $c$ . Find the smallest $c$ for which no collisions occur when inserting these keys.

Exercise 4.8.

A university assigns $2n$ new students to $n$ rooms, numbered $0$ to $n - 1$ , by hashing their IDs. Each ID is a positive integer less than $u$ , with $u$ much larger than $2n$ ; no two students have the same ID, and students choose their own IDs. The university publishes a family $\mathcal{H}$ of hash functions before IDs are chosen, and afterwards chooses the rooming function uniformly from $\mathcal{H}$ . Two students want to be roommates. For each family below, either show that they can choose IDs $k_1, k_2$ that guarantee it, or prove that no choice guarantees it and find the highest probability of being roommates they can achieve.

$\mathcal{H} = \bigl\{\, h_{ab}(k) = (ak + b) \bmod n \;:\; a, b \in \{0, \ldots, n-1\},\ a \neq 0 \,\bigr\}$ .
$\mathcal{H} = \bigl\{\, h_{a}(k) = \bigl(\lfloor kn/u \rfloor + a\bigr) \bmod n \;:\; a \in \{0, \ldots, u-1\} \,\bigr\}$ .

Exercise 4.9.

A wall is lined with $n$ boxes of paper, box $i$ standing $i$ feet from the left end and containing $b_i$ reams, where the $b_i$ are distinct positive integers. A pair of boxes $(b_i, b_j)$ is close if $\lvert i - j \rvert < n/10$ , and it fulfils an order of $r$ reams if $b_i + b_j = r$ . Given $B = (b_0, \ldots, b_{n-1})$ and $r$ , describe an algorithm running in expected $O(n)$ time that decides whether $B$ contains a close pair fulfilling the order.

Exercise 4.10.

Imagine inserting the keys $0, 1, 2, \ldots, n$ , in that order, into a hash table of size $7$ that resolves collisions by chaining, with $h(k) = k \bmod 7$ . Draw the table after the insertion of the keys up to $n = 9$ . Explain how the table evolves for arbitrary $n$ , and derive the worst-case time for the whole operation of inserting the $n + 1$ keys.

Exercises on Graphs

Exercise 4.11.

Construct a $3$ -regular graph on $8$ vertices. Is there a $3$ -regular graph on $9$ vertices?

Exercise 4.12.

Show that every graph whose average degree is $d$ has a subgraph in which every vertex has degree at least $d/2$ .

Exercise 4.13.

Let $G$ be a graph with no loops in which every vertex has the same odd degree $k$ . Show that the number of edges is a multiple of $k$ and that the number of vertices is even.

Exercise 4.14.

Can $7$ line segments be drawn in the plane so that each intersects exactly $5$ others? Prove your answer.
Suppose a simple graph has exactly two vertices of odd degree. Prove that there is a path between them.

Check Yourself

Fresh questions on the whole lesson — none of them is worked out above. Work each one out on paper before opening Python; the box only tells you whether you got there.

Lesson 5

Trees, Searching and Sorting

Taught 24 Sept 2026

Connectivity and Trees

Connectivity

Definition 5.1 (Connected graph).

An undirected graph is connected if every vertex is reachable from every other vertex. By the proposition on walks and simple paths, equivalently, every pair of distinct vertices is joined by a simple path.

Figure 5.1. A graph with two components,

\{a, b, c, d\}

and

\{e, f, g\}

. The accented edge

\{e, f\}

is a bridge.

The graph of Figure 5.1 is disconnected: no path leads from $a$ to $e$ . Its vertices split into $\{a, b, c, d\}$ and $\{e, f, g\}$ .

Definition 5.2 (Connected component).

A connected component is a maximal connected induced subgraph: no further vertex of the graph can be included while keeping it connected. A graph is connected exactly when it has one component, and an isolated vertex forms a component by itself.

Theorem 5.3 (Edges of a connected graph).

A connected simple undirected graph with $n \geqslant 1$ vertices and $m$ edges has $m \geqslant n - 1$ .

Discussion.

The first proof grows the graph from one vertex. At each stage connectivity supplies an edge leaving the part reached so far, and that edge brings in exactly one new vertex, so reaching all $n$ vertices uses $n - 1$ distinct edges of the graph.

The second proof is an induction on $n$ that removes a vertex of smallest degree $k$ . If $k \geqslant 2$ , counting edge-ends gives $m \geqslant n$ directly and no induction is needed. If $k = 1$ , removing a vertex of degree one loses exactly one edge, and what is left is still connected, because a vertex of degree one cannot lie in the middle of a path. The hypothesis then applies to the smaller graph. The hypothesis has to be stated for every connected graph on $n - 1$ vertices, since it is applied to a graph that the proof constructs.

Proof.

Choose one vertex and mark it reached. If fewer than $n$ vertices are reached, connectivity guarantees an edge from some reached vertex to an unreached one; otherwise no path could lead out of the reached set. Mark that new vertex and keep the connecting edge. Each step reaches exactly one new vertex and keeps an edge not kept before. After $n - 1$ steps all $n$ vertices are reached, and we have found $n - 1$ distinct edges of $G$ . Therefore $m \geqslant n - 1$ .

A second proof, by induction, removes a vertex at each step.

Proof.

For each integer $n \geqslant 1$ , let $P(n)$ be the statement: every connected simple undirected graph with $n$ vertices has at least $n - 1$ edges.

Base case, $P(1)$ . A simple graph with one vertex has no pair of distinct vertices to join, so it has $m = 0$ edges. It is connected, and $0 = 1 - 1$ .

Step. Fix $n \geqslant 2$ and assume $P(n-1)$ . Take an arbitrary connected simple graph $G = (S, A)$ with $|S| = n$ and $|A| = m$ , and let $k = \min_{v \in S} d(v)$ be its smallest degree. Because $n \geqslant 2$ , a vertex of degree zero would have no path to any other vertex, contradicting connectivity, so $k \geqslant 1$ . Either $k = 1$ or $k \geqslant 2$ .

Case $k \geqslant 2$ . Every one of the $n$ vertices has degree at least $2$ , so $\sum_{v \in S} d(v) \geqslant 2n$ . Counting edge-ends gives $\sum_{v \in S} d(v) = 2m$ . Therefore $2m \geqslant 2n$ , so $m \geqslant n \geqslant n - 1$ . This case needs neither the removal of a vertex nor $P(n-1)$ .

Case $k = 1$ . Some vertex $v$ has exactly one edge, say $\{v, w\}$ . Remove $v$ and that edge, and call the result $G'$ . No other edge is removed, because no other edge touches $v$ , so $G'$ has $n - 1$ vertices and $m - 1$ edges.

Before applying $P(n-1)$ we check that $G'$ is connected. Take distinct vertices $a, b$ of $G'$ . Since $G$ is connected, a simple path joins $a$ to $b$ in $G$ . Neither endpoint is $v$ , because $a$ and $b$ remain. Nor can $v$ be an internal vertex of the path: the path would have to enter $v$ along one edge and leave along a second, distinct edge, and $v$ has only the edge $\{v, w\}$ . So the path uses neither $v$ nor its edge, and it is a path in $G'$ . This holds for every pair $a, b$ , so $G'$ is connected; when $n = 2$ , $G'$ has a single vertex and is connected by definition.

Now $G'$ satisfies the hypotheses of $P(n-1)$ : it is simple, connected, and has $n - 1$ vertices. Hence $m - 1 \geqslant (n - 1) - 1 = n - 2$ , and adding $1$ to both sides gives $m \geqslant n - 1$ . Both cases prove $P(n)$ from $P(n-1)$ , and with $P(1)$ induction proves the theorem for every $n \geqslant 1$ .

A connected graph with five vertices needs at least four edges, and a path through all five vertices attains the bound. Adding one edge to that path gives five edges and creates a cycle; the theorem does not claim that every connected graph has exactly $n - 1$ edges.

Definition 5.4 (Articulation vertex, bridge and vertex cut).

An articulation vertex is a vertex whose deletion, together with its edges, increases the number of connected components. A bridge, also called an isthmus, is an edge whose deletion increases that number. A vertex cut of a connected graph is a set of vertices whose deletion disconnects it, provided at least two vertices remain afterwards.

In Figure 5.1, the edge $\{e, f\}$ is a bridge: deleting it separates $e$ from $f$ and $g$ . The vertex $f$ is an articulation vertex: deleting it leaves $e$ and $g$ in separate components. All three edges of the left component are bridges too, since that component is a path through four vertices.

Strong Connectivity

For a directed graph, weak connectivity means connectivity once the directions of the arcs are ignored. Requiring directed routes both ways is a stronger condition.

Definition 5.5 (Strong connectivity and the reduced graph).

A directed graph is strongly connected if for every $u, v$ there is a directed walk from $u$ to $v$ and one from $v$ to $u$ . A strongly connected component is a maximal strongly connected induced subgraph. The reduced graph, or condensation, has one vertex for each strongly connected component, and an arc $C \to D$ whenever $C \neq D$ and some arc of the original graph goes from a vertex of $C$ to a vertex of $D$ .

Figure 5.2. The left graph is strongly connected. In the right graph no arc returns towards

d

or leaves

c

, and each vertex is a strongly connected component by itself.

In Figure 5.2, the left graph is strongly connected. In the right one every arc points away from $d$ and towards $c$ , so each of its four vertices is a strongly connected component by itself.

Figure 5.3. A directed graph whose strongly connected components are

\{a, b, c, d\}

and

\{e, f, g\}

, and its reduced graph. The accented arcs are the ones crossing between components.

In Figure 5.3, $\{a, b, c, d\}$ and $\{e, f, g\}$ are each strongly connected, and the only arcs between them point from the first set to the second. The reduced graph has two vertices $C_1, C_2$ and one arc $C_1 \to C_2$ . There cannot be an arc back: that would give reachability both ways and merge the two into one component.

Proposition 5.6 (The reduced graph has no directed cycle).

The reduced graph of any directed graph contains no simple directed cycle.

Discussion.

A cycle through several components would let every vertex in any one of them reach every vertex in the others and come back, so all of them would lie in a single strongly connected component. That contradicts maximality. The proof replaces each arc of the reduced graph by a walk in the original graph.

Proof.

The reduced graph has no loops, since its arcs join distinct components. Suppose $C_1 \to C_2 \to \cdots \to C_k \to C_1$ were a simple directed cycle of it with $k \geqslant 2$ . Each arc $C_i \to C_{i+1}$ comes from an arc of the original graph from some vertex of $C_i$ to some vertex of $C_{i+1}$ , and within each component any two vertices are joined by walks both ways. Concatenating, any vertex of $C_1$ can reach any vertex of $C_2$ , and any vertex of $C_2$ can reach any vertex of $C_1$ around the rest of the cycle. So $C_1 \cup C_2$ induces a strongly connected subgraph larger than $C_1$ , contradicting the maximality of $C_1$ .

Problem 5.1.

Show that a simple undirected graph on $n$ vertices with more than $\binom{n-1}{2}$ edges is connected, and give a disconnected graph with exactly $\binom{n-1}{2}$ edges.

Problem 5.2.

Find the strongly connected components and the reduced graph of the graph in Figure 4.8 of Lesson 4.

Trees

Definition 5.7 (Tree and forest).

A tree is a connected acyclic undirected graph. A forest is an undirected graph whose components are trees.

Figure 5.4. A tree on seven vertices (left), and the out-arborescence obtained by orienting its edges away from

a

(right).

The tree on the left of Figure 5.4 has seven vertices and six edges.

Proposition 5.8 (Counting the edges of a forest).

An acyclic undirected graph with $n$ vertices, $m$ edges and $c$ components satisfies $n = m + c$ .

Discussion.

The proof is an induction on the number of edges, and the step removes one. In an acyclic graph every edge is a bridge: if its endpoints were still joined after deleting it, that route together with the edge would be a cycle. So deleting an edge lowers $m$ by one and raises $c$ by one, and $m + c$ is unchanged. The base case, a graph with no edges, has every vertex as its own component.

Proof.

For $m = 0$ every vertex is its own component, so $c = n$ and $n = m + c$ . Assume the formula for all acyclic graphs with $m - 1$ edges, and take one with $m > 0$ edges. Delete one edge. Its endpoints cannot remain joined by another path, or that path together with the deleted edge would be a cycle. Hence the component containing the edge splits in two and the number of components rises from $c$ to $c + 1$ . The remaining graph is acyclic with $m - 1$ edges, so the hypothesis gives $n = (m - 1) + (c + 1) = m + c$ .

In particular a forest with $n$ vertices and $c$ components has $n - c$ edges.

Theorem 5.9 (Six characterisations of a tree).

Let $G$ be a finite simple undirected graph with $n \geqslant 1$ vertices. The following are equivalent.

$G$ is connected and acyclic.
$G$ is acyclic and has $n - 1$ edges.
$G$ is connected and has $n - 1$ edges.
$G$ is acyclic, and adding any missing edge creates exactly one simple cycle.
$G$ is connected, and deleting any edge disconnects it.
Every pair of distinct vertices is joined by exactly one simple path.

In particular each condition characterises a tree. For $K_1$ the clauses about adding or deleting an edge are vacuous.

Discussion.

Six conditions are proved equivalent by a cycle of implications, $1 \Rightarrow 6 \Rightarrow 5 \Rightarrow 4 \Rightarrow 2 \Rightarrow 3 \Rightarrow 1$ , so that each follows from each. The proof uses two facts. One is the relation between a cycle and two different paths between the same vertices: a cycle gives two routes around it, and two different paths give a cycle where they separate and rejoin. The other is the edge count $n = m + c$ for acyclic graphs, which converts between “has $n - 1$ edges” and “has one component”. The last implication, $3 \Rightarrow 1$ , uses the growing argument from the edge bound for connected graphs: it produces $n - 1$ edges forming a connected acyclic spanning subgraph, and a graph with only $n - 1$ edges has no others.

Proof.

$1 \Rightarrow 6$ . Connectivity supplies a simple path between every pair. If two different simple paths joined the same pair, follow them from the common start until they first diverge, and then along the first until it next meets the second; the two segments between those meeting points form a cycle. Thus the path is unique.

$6 \Rightarrow 5$ . $G$ is connected by 6. The unique simple path between the endpoints of an edge is that edge itself, so deleting it leaves the endpoints with no path between them.

$5 \Rightarrow 4$ . If $G$ had a cycle, deleting one of its edges would leave the endpoints of that edge connected along the rest of the cycle, so it would not disconnect $G$ . So $G$ is acyclic. By connectivity a simple path joins the endpoints of any missing edge, and adding the edge closes the path into a simple cycle. Now $G$ is connected and acyclic, so by $1 \Rightarrow 6$ that path is unique, and every simple cycle through the new edge consists of the new edge and a simple path of $G$ between its endpoints; so the new simple cycle is unique.

$4 \Rightarrow 2$ . If $G$ had two components, adding an edge between them would create no cycle, contrary to 4. Thus $c = 1$ , and since $G$ is acyclic the edge count $n = m + c$ gives $m = n - 1$ .

$2 \Rightarrow 3$ . Since $G$ is acyclic, the edge count gives $c = n - m = n - (n - 1) = 1$ . One component means that $G$ is connected.

$3 \Rightarrow 1$ . Because $G$ is connected, start at one vertex and repeatedly add an edge to a new vertex until every vertex is reached, as in the first proof of the edge bound. The chosen edges form a spanning subgraph with exactly $n - 1$ edges, one for each vertex other than the first. It is connected, since every vertex was joined to one reached earlier, and acyclic, since each edge was added to a new vertex and so cannot close a cycle among those already reached. Since $G$ itself has exactly $n - 1$ edges, it has no others, so $G$ is this subgraph and is acyclic.

In the tree of Figure 5.4 the unique path from $d$ to $f$ is $d, b, c, g, f$ , of length $4$ . Removing $\{b, c\}$ separates it into two components of sizes $3$ and $4$ . Adding the missing edge $\{d, g\}$ creates the unique cycle $d, b, c, g, d$ .

Rooted Trees

Definition 5.10 (Out-arborescence).

An out-arborescence rooted at $r$ is a directed graph in which there is exactly one directed simple path from $r$ to each vertex, and whose underlying undirected graph is a tree. Equivalently, $r$ has in-degree zero, every other vertex has in-degree one, and every vertex is reachable from $r$ . It has $n - 1$ arcs.

Orienting the tree of Figure 5.4 away from $a$ , as $a \to b$ , $b \to c$ , $b \to d$ , $c \to e$ , $c \to g$ and $g \to f$ , gives the out-arborescence with root $a$ on the right of the figure.

Definition 5.11 (Rooted and binary trees).

A rooted tree is a tree with one vertex $r$ chosen as its root. For a vertex $v \neq r$ , the vertex before $v$ on the unique path from $r$ to $v$ is the parent of $v$ , and $v$ is a child of its parent. A vertex with no children is a leaf, and the others are internal. The depth of $v$ is $d(r, v)$ , the length of the path from $r$ to $v$ , and the height of the tree is the largest depth of a vertex. The subtree at $v$ consists of $v$ and every vertex whose path from $r$ passes through $v$ , rooted at $v$ .

A binary tree is a rooted tree in which every vertex has at most two children, each labelled as a left child or a right child, with at most one of each. It is full if every internal vertex has exactly two children.

Orienting each edge of a rooted tree from parent to child gives an out-arborescence rooted at $r$ , since the unique path from $r$ to $v$ in the tree becomes the unique directed path. The subtrees at the children of the root of a binary tree are again binary trees, of height one less at most.

Proposition 5.12 (How large a binary tree of given height can be).

A binary tree of height at most $h$ has at most $2^h$ leaves and at most $2^{h+1} - 1$ vertices.

Discussion.

A binary tree consists of its root and at most two smaller binary trees below it, so both counts are proved by induction on the height. Each subtree at a child of the root has height at most $h - 1$ , so by induction each has at most $2^{h-1}$ leaves and $2^h - 1$ vertices, and there are at most two of them. The leaves of the whole tree are the leaves of the subtrees, unless the root has no children, and the vertices are those of the subtrees plus the root. The recurrence $T(h) = 2T(h-1) + 1$ with $T(0) = 1$ is the Tower of Hanoi recurrence shifted by one.

Proof.

We use induction on $h$ . A binary tree of height $0$ is a single vertex, which is a leaf: $1 = 2^0$ leaves and $1 = 2^1 - 1$ vertices.

Let $h \geqslant 1$ and suppose the claim holds for height at most $h - 1$ . If the root has no children the tree has one leaf and one vertex. Otherwise the root is not a leaf, and every other vertex lies in the subtree at exactly one of the at most two children of the root; each such subtree is a binary tree of height at most $h - 1$ . So there are at most $2 \cdot 2^{h-1} = 2^h$ leaves, and at most $1 + 2\,(2^h - 1) = 2^{h+1} - 1$ vertices.

Corollary 5.13 (Height of a binary tree).

A binary tree with $N$ vertices has height at least $\lceil \log_2 (N+1) \rceil - 1$ , and a binary tree with $K$ leaves has height at least $\lceil \log_2 K \rceil$ .

Proof.

If the height is $h$ , the proposition gives $N \leqslant 2^{h+1} - 1$ , so $h + 1 \geqslant \log_2(N + 1)$ , and since $h + 1$ is an integer, $h + 1 \geqslant \lceil \log_2(N+1) \rceil$ . Likewise $K \leqslant 2^h$ gives $h \geqslant \log_2 K$ , and so $h \geqslant \lceil \log_2 K \rceil$ .

Problem 5.3.

Show that every tree with at least two vertices has at least two leaves, that is, vertices of degree one, and that a full binary tree with $K$ leaves has exactly $K - 1$ internal vertices.

Problem 5.4.

Count the binary trees with $1$ , $2$ , $3$ and $4$ vertices, where two binary trees are the same only if they have the same shape including the left and right labels. Find a recurrence for the number with $N$ vertices by considering the sizes of the two subtrees at the root.

Searching

To search an array $T[0], \ldots, T[n-1]$ for a key $x$ is to return an index $i$ with $\operatorname{key}(T[i]) = x$ , or to report that there is none. This is the find(k) operation of the set interface on an array.

Linear Search

Linear search inspects the entries in order and returns the first index whose key equals $x$ . The entries need not be in any order.

Linear Search
Input:  an array T[0], …, T[n − 1] and a key x.
Output: an index i with key(T[i]) = x, or −1 if there is none.

    for i ≝ 0 to n − 1 do
        if key(T[i]) = x then return i
    return −1

def linear_search(T, x):
    for i in range(len(T)):
        if T[i] == x:
            return i
    return -1

T = [7, 3, 11, 2, 5]
print(linear_search(T, 2), linear_search(T, 4))   # 3 -1

The invariant before the pass for $i$ is that $x$ does not occur among $T[0], \ldots, T[i-1]$ . It holds trivially at $i = 0$ , a pass that does not return extends it by one position, and when the loop ends without returning it says that $x$ does not occur at all. The variant is $n - i$ .

Proposition 5.14 (Cost of linear search).

Linear search on an array of $n$ entries makes at most $n$ comparisons with $x$ , and exactly $n$ when $x$ does not occur. If $x$ occurs exactly once, at each of the $n$ positions with equal likelihood, the mean number of comparisons is $(n+1)/2$ . So linear search takes $\Theta(n)$ time in the worst case and on average.

Discussion.

Each pass makes one comparison, and the pass for $i$ is reached only if $x$ was not among the first $i$ entries, so the count is the position at which the search stops, plus one. The worst case is an absent key, which runs through all $n$ passes. For the mean, a key at position $i$ costs $i + 1$ comparisons, and averaging $1, 2, \ldots, n$ is the sum of an arithmetic progression divided by $n$ .

Proof.

The loop makes one comparison per pass and at most $n$ passes, and it makes all $n$ when no entry has key $x$ . If $x$ occurs exactly once, at position $i$ , the search stops after the $(i+1)$ st comparison. Averaging over the $n$ equally likely positions and using the sum of an arithmetic progression,

\frac{1}{n}\sum_{i=0}^{n-1} (i + 1) = \frac{1}{n} \cdot \frac{n(n+1)}{2} = \frac{n+1}{2} .

Each comparison and each pass cost a bounded number of elementary operations, so the running time is $\Theta(n)$ in both the worst case and the mean.

On an unsorted array no comparison algorithm does better. We prove this with an adversary, as in the second proof of the proposition on finding a maximum.

Proposition 5.15 (Searching an unsorted array).

Every deterministic algorithm that decides whether $x$ occurs in an array of $n$ entries, and learns about the entries only by comparing them with $x$ , compares $x$ with all $n$ entries on some input.

Discussion.

An adversary answers every comparison as though the entry compared were larger than $x$ , and fixes the entries only as far as those answers require. If the algorithm stops before comparing $x$ with some entry, that entry is still free. The adversary then sets it equal to $x$ if the algorithm answered “absent”, and to anything else if it answered “present at that entry”, and in either case the answers given stay true while the output becomes wrong.

Proof.

Answer every comparison of $x$ with an entry $T[j]$ as $x < \operatorname{key}(T[j])$ . Suppose that on these answers the algorithm stops having compared $x$ with only some of the entries, and let $T[k]$ be one it never compared. Every compared entry can be given a key larger than $x$ , consistently with all the answers. If the algorithm reports that $x$ does not occur, give $T[k]$ the key $x$ : the answers are unchanged, so a deterministic algorithm gives the same wrong report. If it reports an index $i$ , then either $T[i]$ was compared and has key larger than $x$ , or $i = k$ and we give $T[k]$ a key different from $x$ ; in both cases the report is wrong. So on some input every entry is compared with $x$ .

Problem 5.5.

Suppose that $x$ is absent with probability $\tfrac12$ , and otherwise lies at each of the $n$ positions with probability $\tfrac{1}{2n}$ . Find the mean number of comparisons made by linear search.

Problem 5.6.

A sentinel search appends $x$ at the end of the array before searching, so that the loop needs no test of the index against $n$ . Write it in Python using append and pop, show that it is correct, and count its comparisons of keys and of indices, compared with the linear search above.

Binary Search

When the array is sorted we can search it by bisection, as in Lesson 3, halving a range of positions instead of an interval of reals.

Let $T[0], \ldots, T[n-1]$ be sorted in nondecreasing key order, meaning $\operatorname{key}(T[0]) \leqslant \operatorname{key}(T[1]) \leqslant \cdots \leqslant \operatorname{key}(T[n-1])$ . Binary search for a target key $x$ keeps a candidate interval of positions $[L, R)$ , that is $L \leqslant i < R$ . It compares $x$ with the key at the middle position $m = L + \lfloor (R - L)/2 \rfloor$ . If they are equal it returns $m$ ; if $x$ is smaller it sets $R = m$ ; otherwise it sets $L = m + 1$ . It returns $-1$ when the interval is empty, $L = R$ .

Binary Search
Input:  an array T[0], …, T[n − 1] sorted by key, and a key x.
Output: an index m with key(T[m]) = x, or −1 if there is none.

    L ≝ 0;  R ≝ n
    while L < R do
        m ≝ L + ⌊(R − L) / 2⌋
        if x = key(T[m]) then return m
        if x < key(T[m]) then R ≝ m
        else L ≝ m + 1
    return −1

def binary_search(T, x):
    L, R = 0, len(T)
    while L < R:
        m = L + (R - L) // 2
        if x == T[m]:
            return m
        if x < T[m]:
            R = m
        else:
            L = m + 1
    return -1

T = [2, 3, 5, 7, 11, 13, 17]
print(binary_search(T, 11), binary_search(T, 4))   # 4 -1

The invariant is: if $x$ occurs in $T$ , then at least one matching index lies in $[L, R)$ . It holds initially, when the interval is the whole array. Sortedness maintains it: if $x < \operatorname{key}(T[m])$ then every position from $m$ on has key at least $\operatorname{key}(T[m]) > x$ and can be discarded, and symmetrically when $x > \operatorname{key}(T[m])$ . At termination either a match has been returned or $[L, R)$ is empty, and then by the invariant $x$ does not occur. The length $R - L$ is a variant: it strictly decreases at every pass. We count one comparison per pass, a three-way comparison of $x$ with $\operatorname{key}(T[m])$ whose outcomes are smaller, equal and larger.

Theorem 5.16 (Binary search takes $O(\log n)$ comparisons).

For $n \geqslant 1$ , binary search on a sorted array of length $n$ makes at most $\lfloor \log_2 n \rfloor + 1$ passes of its loop.

Discussion.

The proof is the one for the convergence of bisection, with the length of the interval in place of its width. Because the middle position is removed from the interval, a pass leaves at most $\lfloor \ell/2 \rfloor$ of the $\ell$ positions rather than exactly half. After $t$ passes the length is therefore at most $\lfloor n/2^t \rfloor$ , which is zero once $2^t > n$ , and the least such $t$ is $\lfloor \log_2 n \rfloor + 1$ .

Proof.

Let $\ell = R - L \geqslant 1$ at the start of a pass, so that $m - L = \lfloor \ell/2 \rfloor$ . If the pass does not return, the new interval is $[L, m)$ , of length $\lfloor \ell/2 \rfloor$ , or $[m+1, R)$ , of length $\ell - \lfloor \ell/2 \rfloor - 1 = \lceil \ell/2 \rceil - 1 \leqslant \lfloor \ell/2 \rfloor$ . So after each pass the length is at most $\lfloor \ell / 2 \rfloor$ , and since $\bigl\lfloor \lfloor a \rfloor / 2 \bigr\rfloor = \lfloor a/2 \rfloor$ for $a \geqslant 0$ , after $t$ passes it is at most $\lfloor n / 2^t \rfloor$ . For $t = \lfloor \log_2 n \rfloor + 1$ we have $2^t > n$ , so the length is $0$ and the loop has stopped.

The bound is attained, for example by an unsuccessful search for a key smaller than every key in the array: it moves left at every pass, and the length goes $n, \lfloor n/2 \rfloor, \lfloor n/4 \rfloor, \ldots$ down to $0$ .

Figure 5.5. The indices binary search tests on an array of length

7

. A search starts at the root and moves left when the target is smaller than the tested key and right when it is larger; it may stop at any vertex on finding the target.

For $n = 7 = 2^3 - 1$ the positions tested form the binary tree of Figure 5.5: the root is the first position tested, and the left and right children of a position are the ones tested next when the target is smaller or larger. A search that stops at depth $t$ has made $t + 1$ comparisons.

Proposition 5.17 (Mean cost of a successful search).

Let $n = 2^k - 1$ and suppose the target is one of the $n$ keys, each equally likely, with all keys distinct. The mean number of comparisons made by binary search is

\frac{1}{2^k - 1} \sum_{i=1}^{k} i\, 2^{i-1} = k - 1 + \frac{k}{2^k - 1} .

Discussion.

For $n = 2^k - 1$ every interval that arises has odd length and splits into two equal halves, so the tree of tested positions is full, with $2^{i-1}$ positions at depth $i - 1$ for $i = 1, \ldots, k$ , and a target at depth $i - 1$ is found after $i$ comparisons. That gives the sum. To evaluate $S_k = \sum_{i=1}^{k} i\,2^{i-1}$ we proceed as for the geometric sum and compare $S_k$ with $2S_{k-1}$ , whose terms are those of $S_k$ shifted by one place with the multiplier lowered by one, so that the difference is a geometric sum.

Proof.

An interval of length $2^j - 1$ with $j \geqslant 2$ has middle position with $2^{j-1} - 1$ positions on each side, so by induction on $j$ the positions tested form a full binary tree with $2^{i-1}$ positions at depth $i - 1$ , for $1 \leqslant i \leqslant k$ . The target at a position of depth $i - 1$ is found at the $i$ th comparison, so the total over the $n$ equally likely targets is $S_k = \sum_{i=1}^{k} i\,2^{i-1}$ .

For $k \geqslant 2$ ,

S_k - 2S_{k-1} = \sum_{i=1}^{k} i\,2^{i-1} - \sum_{i=2}^{k} (i-1)\,2^{i-1} = 1 + \sum_{i=2}^{k} 2^{i-1} = 2^k - 1

by the geometric sum. So $S_k = 2S_{k-1} + 2^k - 1$ with $S_1 = 1$ , and induction gives $S_k = (k-1)2^k + 1$ : at $k = 1$ both sides are $1$ , and $2\bigl((k-2)2^{k-1} + 1\bigr) + 2^k - 1 = (k-1)2^k + 1$ . Finally $(k-1)2^k + 1 = (k-1)(2^k - 1) + k$ , and dividing by $2^k - 1$ gives the stated mean.

The mean is $\Theta(\log n)$ . For arbitrary $n$ interval halving gives an $O(\log n)$ worst case, by the theorem. For a lower bound on the mean, the positions found within $t$ comparisons are those of depth less than $t$ in the tree of tested positions, and by the proposition on binary trees there are at most $2^t - 1$ of them. Take $t = \lfloor \log_2 n \rfloor - 1$ for $n \geqslant 4$ ; then $2^t - 1 < n/2$ , so fewer than half the $n$ positions are found within $t$ comparisons. At least half need more than $t$ , and the mean over equally likely targets is $\Omega(\log n)$ .

A Lower Bound for Searching

A deterministic comparison search algorithm can be pictured as a fixed binary decision tree of all its possible executions, in which each internal vertex is a comparison the algorithm makes. The algorithm walks down the tree from the root: the first comparison it makes is at the root, and according to the outcome it continues at one of the two children. It stops on reaching a leaf, which records its output, so there must be a leaf for every possible output. The number of comparisons on a given input is the depth of the leaf reached, and the worst-case number is the height of the tree.

Theorem 5.18 (Searching needs $\Omega(\log n)$ comparisons).

Every deterministic algorithm that searches a set of $n$ items with distinct keys for a given key, using only comparisons of keys, makes at least $\lceil \log_2(n+1) \rceil$ comparisons on some input.

Discussion.

The proof counts outputs. A search can end in $n + 1$ different ways, one for each stored item and one for “not present”, and each must appear at some leaf of the decision tree. A binary tree with that many leaves has height at least $\log_2(n+1)$ by the corollary on heights, and height is the worst-case number of comparisons.

Proof.

The algorithm has $n + 1$ possible outputs, the $n$ stored items and the report that no item has the key, and each occurs for some input, so its decision tree has at least $n + 1$ leaves. By the corollary on heights of binary trees its height is at least $\lceil \log_2(n+1) \rceil$ , and some input follows a path of that length.

So binary search makes the least possible number of comparisons, up to a constant factor. The same argument with any fixed number of outcomes per comparison in place of two still gives $\Omega(\log n)$ . Hashing does better because it is not a comparison algorithm: reading a direct access array at an index computed from the key can go to any one of its slots in a single step.

Problem 5.7.

Modify binary_search so that it returns the least index $i$ with $\operatorname{key}(T[i]) \geqslant x$ , or $n$ if there is none, still in $O(\log n)$ time. State the invariant, and use your function to count the entries of a sorted array lying in an interval $[a, b)$ .

Problem 5.8.

A programmer writes L = m in place of L = m + 1. Give an array and a key for which the modified loop never terminates, and say which part of the termination argument fails.

Sorting

The Sorting Problem

We sort records, each carrying a key that can be compared with other keys. A comparison sort learns about the keys only by comparing them, as in the comparison model.

Definition 5.19 (Sorting, in place and stable).

A sort returns the same records as its input, rearranged in nondecreasing key order. A sort is in place if it uses $O(1)$ auxiliary cells besides the input array, apart from stack space for recursion if that is being counted separately. A sort is stable if records with equal keys keep their input order.

Checking only that the output keys are in order is not enough to certify a sort: the output must also be a rearrangement of the input records, with none lost or duplicated. Stability can be forced in any comparison sort by comparing the pairs $(\text{key}, \text{original index})$ lexicographically, first by key and then by index, though storing the original indices may change the space requirements.

Example 5.20 (Stable and unstable).

Sorting $(2, a), (1, b), (2, c)$ stably by the numeric key gives $(1, b), (2, a), (2, c)$ : the two records with key $2$ remain in their original relative order. A routine that returns $(1, b), (2, c), (2, a)$ has sorted the records, but not stably.

A rearrangement of $n$ records is a permutation, written as the list $\pi_1, \ldots, \pi_n$ of the input positions in output order, and there are $n!$ of them. A brute-force method tests permutations one by one until it finds an arrangement in increasing order of pairwise distinct keys. A candidate may need $n - 1$ comparisons of adjacent keys to certify that it is sorted, and there are $n!$ candidates.

Definition 5.21 (Inversion).

An inversion of an array $T[0], \ldots, T[n-1]$ is a pair of positions $i < j$ with $\operatorname{key}(T[i]) > \operatorname{key}(T[j])$ .

A sorted array has no inversions, and an array of distinct keys in decreasing order has all $\binom{n}{2}$ possible ones, one for each unordered pair of positions. An exchange of two adjacent records $T[j], T[j+1]$ with $\operatorname{key}(T[j]) > \operatorname{key}(T[j+1])$ removes exactly one inversion, that pair itself, since the relative order of every other pair is unchanged.

Selection Sort

Selection sort repeatedly removes the largest remaining key and puts it at the next final position from right to left. Having already sorted the largest items into the subarray A[i+1:], it scans A[:i+1] for the largest item not yet placed and swaps it with A[i].

Selection Sort
Input:  an array A[0], …, A[n − 1].
Output: the same array, sorted.

    for i ≝ n − 1 down to 1 do
        m ≝ i
        for j ≝ 0 to i − 1 do
            if key(A[m]) < key(A[j]) then m ≝ j
        swap A[m] and A[i]

def selection_sort(A):
    for i in range(len(A) - 1, 0, -1):   # O(n) passes
        m = i                            # O(1) index of the largest so far
        for j in range(i):               # O(i) search A[:i] for a larger item
            if A[m] < A[j]:              # O(1)
                m = j                    # O(1) new largest found
        A[m], A[i] = A[i], A[m]          # O(1) swap

A = [5, 2, 9, 1, 5, 6]
selection_sort(A)
print(A)   # [1, 2, 5, 5, 6, 9]

The invariant before the pass for $i$ is that A[i+1:] holds the $n - 1 - i$ largest records in sorted order, and that every key in A[:i+1] is at most every key in A[i+1:]. The pass moves the largest key of A[:i+1] to position $i$ , which extends the sorted suffix by one. When the loop ends, at $i = 0$ , the suffix A[1:] is sorted and A[0] holds the smallest key.

Finding the maximum among $k$ remaining keys takes $k - 1$ comparisons, which is the least possible by the proposition on finding a maximum, so the method uses

\sum_{k=1}^{n} (k - 1) = \frac{n(n-1)}{2} = \Theta(n^2)

comparisons, even on an input that is already sorted. It performs at most $n - 1$ swaps. It is in place: apart from the array it uses the names i, j and m.

Example 5.22 (Selection on $(1, 2, 4)$ ).

On $(1, 2, 4)$ , selection chooses $4$ , then $2$ , then $1$ . Each chosen maximum occupies its final, rightmost open position, and the comparison counts are $2 + 1 + 0 = 3$ .

Selection sort, swapping as above, is not stable. On the records $(2, a), (1, b), (1, c)$ , compared by key alone, the first pass finds $(2, a)$ at position $0$ as the maximum and swaps it with $(1, c)$ at position $2$ , giving $(1, c), (1, b), (2, a)$ ; the second pass makes no change, and $(1, c)$ ends before $(1, b)$ .

Bubble Sort

A left-to-right pass of bubble sort compares $T[j]$ with $T[j+1]$ and exchanges them if they are out of order. The largest key in the scanned part moves to its right end, so a full pass places the maximum of the active prefix at its final position. Repeating on successively shorter prefixes sorts the array. If a pass makes no exchange, the array is already sorted and the algorithm can stop early.

Bubble Sort
Input:  an array T[0], …, T[n − 1].
Output: the same array, sorted.

    for last ≝ n − 1 down to 1 do
        changed ≝ false
        for j ≝ 0 to last − 1 do
            if key(T[j]) > key(T[j + 1]) then
                swap T[j] and T[j + 1];  changed ≝ true
        if not changed then stop

def bubble_sort(T):
    for last in range(len(T) - 1, 0, -1):
        changed = False
        for j in range(last):
            if T[j] > T[j + 1]:
                T[j], T[j + 1] = T[j + 1], T[j]
                changed = True
        if not changed:
            return

The invariant before the pass with a given last is that T[last+1:] holds the largest records in sorted order, each at least every key in T[:last+1].

For $n \geqslant 1$ , the worst-case number of comparisons is $n(n-1)/2$ , and the best case, on a sorted input, is $n - 1$ with the early stop. Over the $n!$ orders of $n$ distinct keys, counted equally, the mean number of comparisons is still $\Theta(n^2)$ . For the lower bound, the smallest key begins in the last half of the array, at one of the $\lceil n/2 \rceil$ positions from $\lfloor n/2 \rfloor$ on, in at least half of the $n!$ orders. A left-to-right pass moves the smallest key left by at most one position, so on those orders at least $\lfloor n/2 \rfloor$ passes are needed, and each of those passes makes at least $n/2$ comparisons. Thus at least half the orders cost at least $\lfloor n/2 \rfloor \cdot n/2$ comparisons, and the mean is $\Omega(n^2)$ . The upper bound $O(n^2)$ holds on every input.

Proposition 5.23 (Exchanges in bubble sort).

The number of exchanges bubble sort makes on an array equals its number of inversions. Over the $n!$ orders of $n$ distinct keys, counted equally, the mean number of inversions is $n(n-1)/4$ .

Discussion.

For the first statement, every exchange removes exactly one inversion, and the algorithm stops with a sorted array, which has none; so the number of exchanges is the number of inversions at the start. For the mean, pair each order with its reverse. A pair of positions is inverted in exactly one of the two, so the inversion counts of an order and of its reverse add up to $\binom{n}{2}$ . The reversal pairs the $n!$ orders off, so the average over all of them is half of $\binom{n}{2}$ .

Proof.

Bubble sort exchanges $T[j]$ and $T[j+1]$ only when $\operatorname{key}(T[j]) > \operatorname{key}(T[j+1])$ , and such an exchange of adjacent records removes exactly one inversion. It stops with a sorted array, which has no inversions. So if the input has $I$ inversions, it makes exactly $I$ exchanges.

For an order $\pi$ of distinct keys let $\operatorname{inv}(\pi)$ be its number of inversions, and let $\bar\pi$ be the reverse order. For each of the $\binom{n}{2}$ pairs of keys, exactly one of $\pi$ and $\bar\pi$ lists the larger key first, so $\operatorname{inv}(\pi) + \operatorname{inv}(\bar\pi) = \binom{n}{2}$ . Reversal is a bijection from the set of orders to itself, so summing over all orders,

2\sum_{\pi} \operatorname{inv}(\pi) = \sum_{\pi} \bigl(\operatorname{inv}(\pi) + \operatorname{inv}(\bar\pi)\bigr) = n!\binom{n}{2},

and the mean is $\tfrac12\binom{n}{2} = n(n-1)/4$ .

Exchanges happen only on strict inversions, so records with equal keys are never exchanged with each other and keep their original order: bubble sort is stable. Small keys near the right end move slowly, one position per pass, and are sometimes called turtles; large keys near the left move quickly to the right and are called hares. Bidirectional bubble sort alternates the direction of its passes to move turtles faster, and gnome sort steps back to recheck the previous adjacent pair after each exchange.

Insertion Sort

Insertion sort treats T[0..i-1] as sorted and inserts T[i] into that prefix by shifting the larger records one position right.

Insertion Sort
Input:  an array T[0], …, T[n − 1].
Output: the same array, sorted.

    for i ≝ 1 to n − 1 do
        x ≝ T[i];  j ≝ i − 1
        while j ⩾ 0 and key(x) < key(T[j]) do
            T[j + 1] ≝ T[j];  j ≝ j − 1
        T[j + 1] ≝ x

def insertion_sort(T):
    for i in range(1, len(T)):           # O(n) passes
        x = T[i]                         # the record to insert
        j = i - 1
        while j >= 0 and x < T[j]:       # O(i) shift larger records right
            T[j + 1] = T[j]
            j = j - 1
        T[j + 1] = x                     # fill the gap

The invariant before the pass for $i$ is that T[0..i-1] holds the first $i$ input records in sorted order. The final assignment T[j+1] = x places the saved record in the gap left by the shifts, and it is essential: writing $x$ anywhere else would duplicate one record and lose another. The while test relies on and stopping as soon as j >= 0 is False, so that T[-1] is never read.

Example 5.24 (Insertion on $(4, 2, 3)$ ).

On $(4, 2, 3)$ , save $2$ , shift $4$ right and write $2$ at index $0$ , giving $(2, 4, 3)$ . Next save $3$ , shift $4$ right and write $3$ at index $1$ , giving $(2, 3, 4)$ .

Insertion sort is $\Theta(n^2)$ in the worst case, on an input in decreasing order, where the pass for $i$ shifts all $i$ records of the prefix, and $\Theta(n)$ on an already sorted input, where every pass makes one comparison and no shift.

In Place and Stable

Selection sort, bubble sort and insertion sort are all in place: each uses a constant amount of space besides the array, and acts on the array only by comparisons and by exchanging or moving records. Bubble sort and insertion sort are stable, insertion sort because a record is never shifted past one with an equal key. Selection sort, as implemented above, is not.

Problem 5.9.

Show that insertion sort performs exactly as many shifts T[j + 1] = T[j] as the input has inversions, and deduce the mean number of shifts over the $n!$ orders of $n$ distinct keys. Give an input of length $n$ on which selection sort makes $n - 1$ swaps and insertion sort makes no shift.

Problem 5.10.

Run bubble sort and insertion sort on $(3, 1, 4, 1, 5, 9, 2, 6)$ , keeping the two $1$ s apart as $1_a$ and $1_b$ . Record the array after each pass of each algorithm, count the comparisons and exchanges or shifts, and confirm that both outputs keep $1_a$ before $1_b$ .

Merge Sort

Merge sort splits the array in half, sorts each half recursively, and merges the two sorted halves into one.

Proposition 5.25 (Merging two sorted arrays).

Two sorted arrays of lengths $a, b > 0$ can be merged into one sorted array with at most $a + b - 1$ key comparisons. If ties take the record from the left array first, the merge is stable.

Discussion.

The smallest remaining record of the whole is always at the front of one of the two arrays, because each array is sorted, so one comparison of the two front records decides which comes next. Each comparison outputs one record, and once one array is exhausted the rest of the other is copied without comparing. At least one record, the last, is output without a comparison, which gives $a + b - 1$ . For stability, when the two front keys are equal, taking the left one keeps records from the left array ahead of equal records from the right.

Proof.

Keep a cursor at the first unmerged element of each array. While both arrays have elements left, compare their current heads and copy the smaller one to the output. Its key is no larger than any remaining key, because each input array is already sorted. So the output stays sorted, and no record is lost or copied twice. Each comparison advances one cursor, so after at most $a + b - 1$ comparisons one array must be empty; the other array’s sorted tail is then appended without further comparisons. On equal keys, choosing the left head first preserves the original order between the two arrays, while the order within each array is unchanged.

Merge
Input:  sorted arrays X and Y.
Output: a sorted array Z holding the records of X and Y.

    i ≝ 0;  j ≝ 0;  Z ≝ empty
    while i < length(X) and j < length(Y) do
        if key(X[i]) ⩽ key(Y[j]) then append X[i] to Z;  i ≝ i + 1
        else append Y[j] to Z;  j ≝ j + 1
    append the remaining part of X, then of Y, to Z
    return Z

Merge Sort
Input:  an array A.
Output: a sorted array holding the records of A.

    if length(A) ⩽ 1 then return A
    h ≝ ⌊length(A) / 2⌋
    return Merge(Merge Sort(A[0..h − 1]), Merge Sort(A[h..length(A) − 1]))

def merge(X, Y):
    i, j, Z = 0, 0, []
    while i < len(X) and j < len(Y):
        if X[i] <= Y[j]:
            Z.append(X[i])
            i = i + 1
        else:
            Z.append(Y[j])
            j = j + 1
    return Z + X[i:] + Y[j:]

def merge_sort(A):
    if len(A) <= 1:
        return A
    h = len(A) // 2
    return merge(merge_sort(A[:h]), merge_sort(A[h:]))

print(merge_sort([15, 5, 64, 8, 12, 6, 4, 35]))   # [4, 5, 6, 8, 12, 15, 35, 64]

Theorem 5.26 (Merge sort).

On an array of $n$ records with comparable keys, merge sort returns a sorted rearrangement of the input, and choosing the left head on equal keys makes it stable. It uses $O(n \log n)$ time and $O(n)$ auxiliary storage. For $n = 2^k$ , its worst-case number of key comparisons is exactly $n \log_2 n - n + 1$ .

Discussion.

Correctness is an induction on $n$ whose step is the merge proposition: the recursive calls are on shorter arrays, so by the hypothesis they return sorted rearrangements of the halves, and merging those gives a sorted rearrangement of the whole. For the time, we count level by level: the arrays at one level are disjoint pieces of the input, so merging all of them costs $O(n)$ , and halving gives about $\log_2 n$ levels. For the exact count, the merge proposition allows a merge of two halves of size $2^{k-1}$ up to $2^k - 1$ comparisons, which gives the recurrence $C_k = 2C_{k-1} + 2^k - 1$ . It remains to find an input that attains the bound at every merge, and to solve the recurrence.

Proof.

We prove correctness by induction on $n$ . For $n \leqslant 1$ the array is already sorted. If $n > 1$ , both halves have fewer than $n$ elements, so the recursive calls terminate and, by induction, return sorted rearrangements of their halves. The merge proposition combines those into a sorted rearrangement of the whole input. Its tie rule preserves the order of equal-key records across the halves, so induction also proves stability. The recursion terminates because every call on more than one record is made on strictly shorter arrays.

At any fixed level of the recursion the subarrays are disjoint parts of the original array, so their lengths add up to at most $n$ . Merging each costs time proportional to its length, so the total work per level is $O(n)$ . Halving gives at most $\lceil \log_2 n \rceil$ levels of merging, and therefore $O(n \log n)$ time. At any instant the arrays alive along the current chain of calls have lengths at most $n, n/2, n/4, \ldots$ together with their merge outputs, so at most $O(n)$ auxiliary storage is present at once; the recursion stack has $O(\log n)$ frames.

When $n = 2^k$ , a merge of two sorted halves of equal size can need all $2^k - 1$ comparisons the merge proposition allows: give the left half the records of odd rank and the right half those of even rank, so that their sorted values alternate until only one remains. Apply the same odd–even assignment recursively within each half. Arranging the input by these assignments makes every merge attain its worst case. Writing $C_k$ for the worst case at size $2^k$ , this gives $C_0 = 0$ and

C_k = 2C_{k-1} + 2^k - 1 .

We claim $C_k = k2^k - 2^k + 1$ . At $k = 0$ both sides are $0$ . Assuming the formula at $k - 1$ ,

C_k = 2\bigl((k-1)2^{k-1} - 2^{k-1} + 1\bigr) + 2^k - 1 = k2^k - 2^k + 1 .

With $n = 2^k$ this is $n \log_2 n - n + 1$ . It is a count of key comparisons, and an array of one record makes none.

Problem 5.11.

Write an iterative merge sort that merges adjacent runs of length $1$ , then $2$ , then $4$ , and so on, with no recursion. Prove it correct with a loop invariant on the run length, and show that it makes at most $n \lceil \log_2 n \rceil$ comparisons.

Quicksort

Quicksort chooses a pivot, partitions the array so that smaller keys precede the pivot and larger or equal keys follow it, and then recursively sorts the two sides. For the partition in place, with the pivot initially at position $L$ , the invariant before inspecting position $k$ is: positions $L+1, \ldots, p$ hold keys smaller than the pivot, positions $p+1, \ldots, k-1$ hold keys larger than or equal to it, and positions $k, \ldots, R-1$ are unexamined. A newly found smaller record is swapped into position $p + 1$ and $p$ is increased. At the end the pivot is swapped with the record at position $p$ . Partitioning $s$ records compares each of the other $s - 1$ records with the pivot once.

The pseudocode below sorts the half-open slice $[L, R)$ of the original array in place; no slice is copied. The partition moves only records strictly smaller than the pivot to its left.

Quicksort
Input:  an array A and positions L ⩽ R.
Output: A with A[L..R − 1] sorted.

    Sort(A, L, R):
        if R − L ⩽ 1 then return
        choose q uniformly from L, …, R − 1;  swap A[L] and A[q]
        pivot ≝ A[L];  p ≝ L
        for k ≝ L + 1 to R − 1 do
            if key(A[k]) < key(pivot) then
                p ≝ p + 1;  swap A[p] and A[k]
        swap A[L] and A[p]
        Sort(A, L, p);  Sort(A, p + 1, R)

The statement from random import randrange makes randrange available: randrange(L, R) returns an integer chosen uniformly from $L, \ldots, R - 1$ , the same range as range(L, R).

from random import randrange

def sort_slice(A, L, R):
    if R - L <= 1:
        return
    q = randrange(L, R)
    A[L], A[q] = A[q], A[L]
    pivot = A[L]
    p = L
    for k in range(L + 1, R):
        if A[k] < pivot:
            p = p + 1
            A[p], A[k] = A[k], A[p]
    A[L], A[p] = A[p], A[L]
    sort_slice(A, L, p)
    sort_slice(A, p + 1, R)

def quicksort(A):
    sort_slice(A, 0, len(A))

If the pivot has rank $r$ among $n$ distinct keys, meaning $r - 1$ keys are smaller, the number of comparisons satisfies

C(n) = n - 1 + C(r - 1) + C(n - r), \qquad C(0) = C(1) = 0 .

Example 5.27 (One partition).

For the input $(15, 5, 64, 8, 12, 6, 4, 35)$ , take the first value $15$ as pivot, with no random swap. The partition puts the five smaller values $5, 8, 12, 6, 4$ before it and $64, 35$ after it, and the in-place result is $(4, 5, 8, 12, 6, 15, 64, 35)$ . Recursively sorting the two sides gives $(4, 5, 6, 8, 12, 15, 35, 64)$ . The order within each side before the recursion depends on the partition routine.

Proposition 5.28 (Worst and best case of quicksort).

For $n$ distinct keys, any run of quicksort makes at most $\binom{n}{2} = n(n-1)/2$ key comparisons. This bound is attained when every pivot is the smallest or largest key in its current subarray, so the worst-case number of comparisons is $\Theta(n^2)$ . If every pivot splits its subarray as evenly as possible, the number of comparisons is $\Theta(n \log n)$ .

Discussion.

For the upper bound we count pairs of keys. Two keys are compared only when one of them is the pivot, and a pivot is left out of all later calls, so no pair is compared twice; there are $\binom{n}{2}$ pairs. When every pivot is extreme, one side of each partition is empty, and the recurrence becomes $W_n = (n-1) + W_{n-1}$ , which sums to the same number. For even splits, the depth of the recursion is logarithmic and each level costs at most $n$ comparisons, which gives $O(n \log n)$ ; the matching lower bound needs a count of how many levels still have large subarrays, and how many comparisons each such level makes.

Proof.

Partitioning a subarray of size $s$ compares its pivot with each of the other $s - 1$ keys exactly once. A given pair of keys can be compared only when one of them is the pivot, and that pivot is then excluded from all recursive subarrays. Thus no pair is compared twice, and there are at most $\binom{n}{2}$ comparisons. If every pivot is extreme, one recursive side is empty and the other has size $n - 1$ . The count obeys $W_n = (n-1) + W_{n-1}$ with $W_0 = W_1 = 0$ , and hence

W_n = (n-1) + (n-2) + \cdots + 1 = \frac{n(n-1)}{2} .

For balanced splits, the recursion has $O(\log n)$ levels. At any level the active subarrays are disjoint, so their sizes add up to at most $n$ and their partitions make at most $n$ comparisons in total. This proves $O(n \log n)$ .

For the reverse bound, number the levels from $\ell = 0$ . A balanced split of $s$ records leaves at least $\lfloor (s-1)/2 \rfloor$ records on either side. Applying this at each level shows that every subarray at level $\ell$ has at least $\lfloor (n+1)/2^\ell \rfloor - 1$ records. For $0 \leqslant \ell \leqslant \lfloor \log_2 n \rfloor - 2$ this is at least $3$ , so no branch has yet ended at a call on one record. Before such a level at most $2^\ell - 1$ pivots have been removed, and the remaining records all belong to at most $2^\ell$ active subarrays. A subarray of size $s$ uses $s - 1$ comparisons, so level $\ell$ uses at least $n - (2^\ell - 1) - 2^\ell = n - 2^{\ell+1} + 1 \geqslant n/2$ comparisons. There are $\Theta(\log n)$ such levels for large $n$ , which proves $\Omega(n \log n)$ .

The in-place partition is not stable in general. The recursive calls use $O(\log n)$ stack space for balanced splits and $O(n)$ when the splits are as uneven as possible.

With a random pivot the cost is an average over the random choices, in the sense of the expectation defined for hashing in the last lesson.

Remark (Expected cost of a randomized algorithm).

The expectation used for hashing is an average over one uniform choice. Randomized quicksort makes a uniform choice at every call, and its expected cost is defined in the same way one call at a time: if a call on $s$ keys chooses the pivot rank $r$ with probability $1/s$ , and the rest of the run then has expected cost $c_r$ , the expected cost of the call is its own comparisons plus $\tfrac{1}{s}\sum_{r} c_r$ . Equivalently, it is the average over all complete runs, each run weighted by the product of the probabilities $1/s$ of the choices it makes.

Theorem 5.29 (Expected cost of randomized quicksort).

Fix any input order of $n$ distinct keys. At every recursive call choose the pivot uniformly from the current subarray, and compare it once with each other key there. Let $E_n$ be the expected total number of key comparisons. Then

E_0 = 0, \qquad E_n = 2(n+1)H_n - 4n \quad (n \geqslant 1) .

In particular $E_n = \Theta(n \log n)$ . The expectation is over the pivot choices; the input order is fixed and need not be random.

Discussion.

The proof has four steps. Conditioning on the rank of the first pivot turns the expectation into a recurrence in which $E_n$ depends on all of $E_0, \ldots, E_{n-1}$ through their sum. Writing the recurrence at $n$ and at $n - 1$ and subtracting removes the sum, leaving a first-order recurrence with variable coefficients, of the kind the summation factor of the last lesson solves; the example there is the same recurrence with $2n$ in place of $2(n-1)$ . Here the answer is checked by induction instead. Finally the bounds on $H_n$ give the growth rate.

Proof.

Step 1: condition on the first pivot. A subarray of size at most $1$ needs no comparisons, so $E_0 = E_1 = 0$ . For $n \geqslant 2$ the first partition costs exactly $n - 1$ comparisons. The pivot is equally likely to have any rank $r \in \{1, \ldots, n\}$ among the keys. Rank $r$ leaves $r - 1$ smaller keys on the left and $n - r$ larger keys on the right. Because every later pivot is chosen uniformly within its own subarray, the expected costs of those two calls are $E_{r-1}$ and $E_{n-r}$ , whatever their internal order. Averaging over the $n$ possible ranks gives

E_n = \frac{1}{n}\sum_{r=1}^{n} \bigl((n-1) + E_{r-1} + E_{n-r}\bigr) = n - 1 + \frac{2}{n}\sum_{j=0}^{n-1} E_j ,

since both $r - 1$ and $n - r$ run once through $0, \ldots, n-1$ as $r$ runs through $1, \ldots, n$ .

Step 2: remove the sum. Multiply this equation by $n$ , and write the same equation for $n - 1$ multiplied by $n - 1$ :

\begin{aligned} nE_n &= n(n-1) + 2\sum_{j=0}^{n-1} E_j, \\ (n-1)E_{n-1} &= (n-1)(n-2) + 2\sum_{j=0}^{n-2} E_j . \end{aligned}

Subtract the second from the first. The two sums differ only by $E_{n-1}$ , while $n(n-1) - (n-1)(n-2) = 2(n-1)$ . Therefore $nE_n - (n-1)E_{n-1} = 2(n-1) + 2E_{n-1}$ , that is,

nE_n = (n+1)E_{n-1} + 2(n-1) .

Step 3: solve by induction. At $n = 1$ the claimed expression is $2 \cdot 2 \cdot H_1 - 4 = 0 = E_1$ . Assume $E_{n-1} = 2nH_{n-1} - 4(n-1)$ for some $n \geqslant 2$ . Substituting into the last recurrence and using $H_{n-1} = H_n - 1/n$ ,

\begin{aligned} nE_n &= (n+1)\bigl(2nH_{n-1} - 4(n-1)\bigr) + 2(n-1) \\ &= 2n(n+1)H_{n-1} - 4n^2 + 2n + 2 \\ &= 2n(n+1)\left(H_n - \frac{1}{n}\right) - 4n^2 + 2n + 2 \\ &= 2n(n+1)H_n - 4n^2 . \end{aligned}

Dividing by $n$ gives $E_n = 2(n+1)H_n - 4n$ .

Step 4: the growth rate. By the bounds on the harmonic numbers, $\tfrac12\lfloor \log_2 n \rfloor \leqslant H_n \leqslant 1 + \log_2 n$ . The upper bound gives $E_n \leqslant 2(n+1)(1 + \log_2 n) = O(n \log n)$ . The lower bound gives $E_n \geqslant (n+1)(\log_2 n - 1) - 4n$ , and for all sufficiently large $n$ the term $(n+1)\log_2 n$ exceeds twice the rest, so $E_n = \Omega(n \log n)$ . Thus $E_n = \Theta(n \log n)$ .

Example 5.30 (Three keys).

For three distinct keys, a smallest or largest first pivot costs two comparisons and leaves a call on two keys costing one more, for a total of $3$ . A middle first pivot costs two comparisons and leaves only calls on one key, for a total of $2$ . The three ranks are equally likely, so $E_3 = (3 + 2 + 3)/3 = 8/3$ . The formula agrees: $2 \cdot 4 \cdot \bigl(1 + \tfrac12 + \tfrac13\bigr) - 12 = 8/3$ .

Problem 5.12.

Show that on the input $(1, 2, \ldots, n)$ quicksort with the first record always taken as pivot makes $n(n-1)/2$ comparisons, and that with a uniformly random pivot the probability of making all $n(n-1)/2$ is $2^{n-1}/n!$ for $n \geqslant 2$ .

Problem 5.13.

Two keys of ranks $i < j$ are compared by randomized quicksort exactly when the first pivot chosen from the keys of ranks $i, \ldots, j$ is one of the two. Deduce that they are compared with probability $2/(j - i + 1)$ , and use linearity of expectation to give a second proof that $E_n = 2(n+1)H_n - 4n$ .

Lower Bounds for Comparison Sorting

A deterministic comparison sort is described, like a comparison search, by a binary decision tree: each internal vertex is a comparison, the two branches below it are its two outcomes, and each leaf records the rearrangement the algorithm outputs. An algorithm may ask a comparison whose result is already forced by earlier answers, and then one branch below it is reached by no input.

Figure 5.6. A comparison tree for three records

a_0, a_1, a_2

. Left branches answer yes and right branches no; a leaf such as

021

means

a_0 \lt a_2 \lt a_1

. The two accented leaves cannot be reached, because the comparison above them was already settled by an earlier answer.

The comparison tree of Figure 5.6 names the compared records $a_0, a_1, a_2$ rather than their changing positions in the array. Its six reachable leaves are the six possible strict orders; the crossed leaves are impossible by transitivity.

Theorem 5.31 (Worst-case lower bound for sorting).

Every deterministic sorting algorithm that learns about $n$ distinct, otherwise arbitrary keys only by comparing pairs makes at least $\lceil \log_2(n!) \rceil$ comparisons on some input. Hence its worst-case number of comparisons is $\Omega(n \log n)$ .

Discussion.

As for searching, the proof counts outputs, and there are now $n!$ of them. Two inputs whose keys are in different relative orders need different rearrangements, so they must reach different leaves, and the decision tree has at least $n!$ reachable leaves. The corollary on heights of binary trees then bounds the height below by $\log_2(n!)$ . For the growth rate, half of the factors of $n!$ are at least $n/2$ , so $\log_2(n!)$ is at least about $\tfrac{n}{2}\log_2 \tfrac{n}{2}$ .

Proof.

There are $n!$ possible relative orders of the distinct input keys: $n$ choices for the rank of the first record, $n - 1$ for the second, and so on. Represent the algorithm by its binary decision tree. Each input follows one path from the root to a leaf, and the length of that path is its number of comparisons. Two different relative orders cannot end at the same leaf: that leaf prescribes one output rearrangement for both, and for at least one of them it is wrong. Therefore the tree has at least $n!$ reachable leaves, and after removing the unreachable branches it is a binary tree with at least $n!$ leaves. By the corollary on heights its height $h$ satisfies $h \geqslant \lceil \log_2(n!) \rceil$ .

The last $\lfloor n/2 \rfloor$ factors of $n! = n(n-1)\cdots 1$ are each at least $n/2$ , so $n! \geqslant (n/2)^{\lfloor n/2 \rfloor}$ and

\log_2(n!) \geqslant \lfloor n/2 \rfloor \log_2(n/2) = \Omega(n \log n) .

Removing the branches that no input can follow, and contracting each vertex left with one child, turns the decision tree into a full binary tree with one leaf per possible outcome.

Figure 5.7. Pruning. Branches that no input can follow are drawn dashed on the left; removing them and contracting each vertex left with a single child gives the full binary tree on the right, with one leaf for each of the four possible outcomes.

Merge sort makes at most $n\lceil \log_2 n\rceil$ comparisons, so it is asymptotically optimal among comparison sorts in the worst case.

The mean number of comparisons over the $n!$ equally weighted orders of distinct keys is the mean depth of the leaves of the decision tree, one leaf per order. A full binary tree with $K$ leaves is balanced if its leaf depths differ by at most one.

Proposition 5.32 (Balanced trees minimise the total depth).

Among full binary trees with $K$ leaves, a balanced one has the least sum of leaf depths, and in a balanced full binary tree with $K$ leaves every leaf has depth at least $\lfloor \log_2 K \rfloor$ .

Discussion.

The first claim is proved by an exchange that lowers the depth sum of an unbalanced tree. If some leaf $c$ is at least two levels above the deepest leaves, move a deepest pair of sibling leaves $a, b$ together with their parent into the place of $c$ , and put $c$ where their parent was. Three depths change, and the sum falls. The depth sum is a nonnegative integer, so the exchange can be repeated only finitely often, and it stops at a balanced tree. For the second claim, look at the shallowest leaf: every level above it is full, and all leaves lie on its level or the next, which bounds $K$ by twice the size of its level.

Proof.

Take a full binary tree that is not balanced. Choose deepest sibling leaves $a, b$ , at depth $p$ , with parent $n$ , and a leaf $c$ at depth $p' \leqslant p - 2$ . Exchange the subtree consisting of $n$ , $a$ and $b$ with the leaf $c$ . The tree remains a full binary tree with the same leaves, $a$ and $b$ move to depth $p' + 1$ , and $c$ moves to depth $p - 1$ . The sum of these three depths changes from $2p + p'$ to $2(p' + 1) + (p - 1)$ , a decrease of $p - p' - 1 > 0$ , and no other depth changes. Repeating the operation reaches a balanced tree, because the nonnegative integer depth sum strictly decreases each time. Every tree with $K$ leaves can be transformed in this way into a balanced one with no larger depth sum, and all balanced full binary trees with $K$ leaves have the same multiset of leaf depths, as the count below shows; so a balanced tree has the least sum.

Let the shallowest leaf of a balanced full binary tree have depth $d$ . There is no leaf above depth $d$ , so every vertex at depth less than $d$ is internal with two children, and depth $d$ holds $2^d$ vertices. The leaves are at depth $d$ or $d + 1$ , and those at depth $d + 1$ are the children of the internal vertices at depth $d$ , so $K = 2^d + \#\{\text{internal vertices at depth } d\}$ . At least one vertex at depth $d$ is a leaf, so $2^d \leqslant K < 2^{d+1}$ . This determines $d = \lfloor \log_2 K \rfloor$ , and with it the number of leaves at each depth, and every leaf has depth at least $\lfloor \log_2 K \rfloor$ .

Figure 5.8. The exchange. The two deepest sibling leaves

a

b

and their parent

n

swap places with a leaf

c

at least two levels higher;

a

and

b

rise to depth

p' + 1

and

c

falls to depth

p - 1

For example, six leaves can occur at depths $2$ and $3$ . The proposition gives the asymptotic bound: the mean depth of any full binary tree with $K$ leaves is at least $\lfloor \log_2 K \rfloor$ , which is $\Omega(\log K)$ . The exact bound $\log_2 K$ is proved differently.

Theorem 5.33 (Average lower bound for sorting).

Suppose the $n!$ relative orders of $n$ distinct keys are equally likely. Every deterministic comparison sort has mean number of comparisons at least $\log_2(n!)$ , and therefore $\Omega(n \log n)$ .

Discussion.

The proof turns the leaf depths into lengths of intervals. Each leaf is reached by a word of left and right choices, and a word of length $d$ picks out a subinterval of $[0, 1)$ of length $2^{-d}$ by halving repeatedly. Since no leaf’s word begins another leaf’s word, the intervals do not overlap, so their lengths add up to at most $1$ . The mean depth is then bounded below by comparing the arithmetic mean of the numbers $2^{-d_i}$ with their geometric mean. The inequality of the means was proved for two numbers in Lesson 1; the proof extends it to $K$ numbers by doubling up to a power of two and padding.

Proof.

Keep one reachable leaf of the decision tree for each of the $K = n!$ relative orders, and let their depths be $d_1, \ldots, d_K$ ; the mean number of comparisons is $K^{-1}\sum_i d_i$ . Each path from the root to a leaf is a word of left and right choices. No leaf’s word can be a prefix of another leaf’s word, because a computation stops when it reaches a leaf. To a word of length $d_i$ associate the subinterval of $[0, 1)$ of length $2^{-d_i}$ obtained by choosing the left or right half at each successive letter. The intervals for distinct leaf words do not overlap, so their total length is at most $1$ :

\sum_{i=1}^{K} 2^{-d_i} \leqslant 1 .

Write $x_i = 2^{-d_i} > 0$ and $A = K^{-1}\sum_i x_i$ , so that $A \leqslant 1/K$ . We need the inequality of arithmetic and geometric means for $K$ positive numbers, $\bigl(\prod_i x_i\bigr)^{1/K} \leqslant A$ . For two numbers $u, v$ it is $\sqrt{uv} \leqslant (u + v)/2$ . For a list of $2^r$ numbers, split it into two equal halves with geometric means $G_1, G_2$ and arithmetic means $A_1, A_2$ ; by induction on $r$ , $G_1 \leqslant A_1$ and $G_2 \leqslant A_2$ , so the whole list has geometric mean $\sqrt{G_1 G_2} \leqslant \sqrt{A_1 A_2} \leqslant (A_1 + A_2)/2$ , its arithmetic mean. For general $K$ , choose a power of two $N \geqslant K$ and append $N - K$ copies of $A$ to the list $x_1, \ldots, x_K$ . The enlarged list still has arithmetic mean $A$ , so the power-of-two case gives $\bigl(\prod_i x_i\bigr) A^{N-K} \leqslant A^N$ , and cancelling the positive factor $A^{N-K}$ gives $\prod_i x_i \leqslant A^K$ .

Substituting $x_i = 2^{-d_i}$ ,

2^{-\frac{1}{K}\sum_i d_i} \leqslant A \leqslant \frac{1}{K} .

Taking base-two logarithms and multiplying by $-1$ , which reverses the inequality, gives $K^{-1}\sum_i d_i \geqslant \log_2 K = \log_2(n!)$ . Finally $\log_2(n!) \geqslant \lfloor n/2 \rfloor \log_2(n/2) = \Omega(n \log n)$ , as in the worst-case bound.

Example 5.34 (Six outcomes).

With six equally likely outcomes, a full binary tree may have two leaves at depth $2$ and four at depth $3$ . Its mean depth is $(2 \cdot 2 + 4 \cdot 3)/6 = 8/3$ , which is at least $\log_2 6 \approx 2.585$ . The same leaf-depth argument applies to the $n!$ possible input orders.

Sorting algorithms that are faster than $n \log n$ exist, such as counting sort and radix sort, but only because they use information about the keys beyond pairwise comparison, for instance that they are small integers usable as array indices.

Problem 5.14.

Draw a decision tree for insertion sort on three distinct keys $a_0, a_1, a_2$ , and give its height and the mean depth of its leaves. Compare both with $\lceil \log_2 3! \rceil$ and $\log_2 3!$ .

Problem 5.15.

Show that five distinct keys can be sorted with $7$ comparisons in the worst case, and that no comparison sort does it with $6$ .

Sorted Arrays as Sets

A sorted array implements the set interface. Building it is sorting, $O(n \log n)$ by merge sort. find(k) is binary search, $O(\log n)$ . The smallest and largest keys are at the two ends, and find_next(k) and find_prev(k) are binary searches for the position where $k$ would go. Inserting or deleting while keeping the order shifts up to $n$ items.

Data structure	`build(X)`	`find(k)`	`insert(x)`, `delete(k)`	`find_min()`, `find_max()`	`find_prev(k)`, `find_next(k)`
Array	$n$	$n$	$n$	$n$	$n$
Sorted array	$n \log n$	$\log n$	$n$	$1$	$\log n$
Direct access array	$u$	$1$	$1$	$u$	$u$
Hash table	$n$ (e)	$1$ (e)	$1$ (a)(e)	$n$	$n$

Each entry is an $O(\cdot)$ bound; (e) marks an expected bound and (a) an amortized one. For the sorted array, find is optimal among comparison algorithms by the lower bound for searching, and the bound does not apply to the hash table, which is not a comparison algorithm.

Problem 5.16.

Implement the set interface on a sorted array as a class Sorted_Array_Set, using merge_sort in build and binary search in find, find_next and find_prev, with the running times of the table.

Exercises on Connectivity and Trees

Exercise 5.1.

How many spanning subgraphs of $K_4$ are trees?

Exercise 5.2.

Prove that every connected graph with at least two vertices has a vertex that is not an articulation vertex.

Exercise 5.3.

Let $n \geqslant 2$ , and let $d_1 \leqslant d_2 \leqslant \cdots \leqslant d_n$ be integers. Show that there is a tree with vertex degrees $d_1, \ldots, d_n$ if and only if $d_1 \geqslant 1$ and $\sum_i d_i = 2n - 2$ .

Exercise 5.4.

Let $T_1, \ldots, T_k$ be subtrees of a tree $T$ , meaning subgraphs that are trees, any two of which have at least one vertex in common. Prove that some vertex lies in every $T_i$ .

Exercise 5.5.

The radius of a connected graph is $\min_{v} \max_{w} d(v, w)$ , the least over all vertices $v$ of the greatest distance from $v$ to another vertex. Let $C_n$ be the cycle on $n$ vertices, with vertices $1, \ldots, n$ and edges $\{i, i+1\}$ and $\{n, 1\}$ . Find the radius and the diameter of $K_6$ , of $C_9$ and of $K_{5,7}$ .

Exercise 5.6.

A directed graph $G$ has $1000$ vertices. Its underlying undirected graph has one connected component of size $700$ , and $G$ has one strongly connected component of size $500$ ; its other strongly connected components are smaller.

Suppose $650$ vertices are reachable from a vertex $u$ . Is $u$ in the component of size $700$ ? Explain.
Is $u$ in the strongly connected component of size $500$ ? Explain.
Suppose $600$ vertices are reachable from a vertex $v$ , and $600$ vertices are reachable from $v$ once every arc is reversed. Is $v$ in the strongly connected component of size $500$ ? Explain.
Prove that for every vertex $w$ of the component of size $700$ , there is a directed walk from $v$ to $w$ or one from $w$ to $v$ .

Exercise 5.7.

The divisibility graph $D(n)$ has vertices $1, 2, \ldots, n$ and an edge between $i \neq j$ whenever one of them divides the other.

Draw $D(12)$ . How many connected components does it have, and what is the size of its largest clique?
Prove that for every $d \geqslant 2$ , a graph with no loops in which every vertex has degree at least $d$ contains a simple cycle through at least $d + 1$ vertices.

Exercises on Searching

Exercise 5.8.

A narrow island runs north–south for $n$ kilometres, and a searcher must locate a friend to the nearest kilometre. A tracking device tells the searcher whether the friend is north or south of the current position, but not how far, and a teleporter jumps to any given kilometre in constant time. If the friend is $k$ kilometres from the nearer end of the island, at kilometre $k$ or $n - k$ , describe an algorithm that finds the friend after visiting $O(\log k)$ locations.

Exercise 5.9.

A ridge is given as an array of $n$ distinct altitudes. A point is a good collection point if it is lower than all its neighbours in the array. Design an algorithm running in $O(\log n)$ time that finds a good collection point, prove it correct, and prove its running time.

Exercises on Sorting

Exercise 5.10.

Implementations of insertion sort and merge sort run on the same machine. On inputs of size $n$ , insertion sort takes $8n^2$ steps and merge sort takes $64\, n \log_2 n$ steps. For which values of $n$ does insertion sort beat merge sort?

Exercise 5.11.

Person $i$ , for $i \in \{1, \ldots, n\}$ , enters a room at time $a_i$ and leaves at time $b_i > a_i$ , all the $a_i, b_i$ being distinct. The lights are off at the start of the day; the first person to enter switches them on, and a person who leaves an empty room switches them off. Given $(a_1, b_1), \ldots, (a_n, b_n)$ , we want the number of times the lights are switched on. Design, and prove correct and costed,

a $\Theta(n^2)$ algorithm, and
an $O(n \log n)$ algorithm.

Exercise 5.12.

For each scenario choose selection sort, insertion sort or merge sort, and justify the choice by asymptotic running time.

A data structure $D$ maintains an extrinsic order on $n$ items, with D.get_at(i) in worst-case $\Theta(1)$ time and D.set_at(i, x) in worst-case $\Theta(n \log n)$ time. Sort the items of $D$ in place.
A static array holds references to $n$ comparable objects, any two of which take $\Theta(\log n)$ time to compare. Sort the references so that the objects appear in nondecreasing order.
A sorted array of $n$ integers, each fitting in a machine word, has had $\log \log n$ exchanges made between pairs of adjacent items. Re-sort it.

Exercise 5.13.

Describe the principle of merge sort, and show the steps it takes to sort the array $(9, 3, 6, 2, 4, 1, 5)$ .
Insertion sort can be seen as a merge sort in which each step splits an array of size $n$ into one of size $1$ , the element to be inserted, and one of size $n - 1$ . By solving the appropriate recurrence, show that this recursive insertion sort takes $O(n^2)$ time, assuming that merging two arrays takes $O(n)$ time.
Show that merge sort on a linked list takes $O(n \log n)$ time, and that it can be done with $O(1)$ auxiliary space apart from the recursion, showing how. A programmer who can merge arrays only with $O(n)$ extra space proposes to convert arrays to linked lists before sorting them, to save space. Comment on this strategy.

Exercise 5.14.

Suppose that quicksort always partitions into two parts of relative sizes $\alpha$ and $1 - \alpha$ , for a constant $0 < \alpha < \tfrac12$ . Ignoring rounding, find the least depth of a leaf in the recursion tree as a function of $n$ and $\alpha$ .
How long does the quicksort of these notes take if all the keys are equal? Explain.
What are the advantages and disadvantages of choosing the pivot at random? How does it affect the worst-case and the average-case running time?

Exercise 5.15.

How would you construct an input that makes randomized quicksort take quadratic time, without access to the state of the random number generator?

Exercise 5.16.

Merge sort can be implemented as the usual two-way merge sort, or as a three-way merge sort that splits its input into three and sorts each part recursively.

Find the worst-case number of comparisons needed to merge two sorted arrays of length $n/2$ .
Find the worst-case number of comparisons needed to merge three sorted arrays of length $n/3$ , both by merging all three at once and by merging in pairs.
Using these, and solving suitable recurrences, find the total number of comparisons made by two-way and by three-way merge sort.
If comparisons dominate the cost, which would you expect to be faster on an arbitrary array?

Exercise 5.17.

Describe an algorithm, running in time strictly better than $O(n^2)$ , that takes a positive integer $s$ and a set $A$ of $n$ positive integers and decides whether two distinct elements of $A$ add up to exactly $s$ . Give its running time.

Exercise 5.18.

Each of $n$ computers has run the same computation, and we want to know whether strictly more than $n/2$ of them arrived at the same result. The only available query takes two computers and reports whether they produced the same result. Design an algorithm that decides this with $O(n \log n)$ queries, prove it correct, and prove the bound on the number of queries.

Exercise 5.19.

Find an asymptotically tight upper bound for the recurrence $T(1) = 1$ , $T(n) = T(n-1) + \log_2 n$ , and explain your answer.

Check Yourself

Fresh questions on the whole lesson — none of them is worked out above. Work each one out on paper before opening Python; the box only tells you whether you got there.

Vectors

Coordinates

Vector Algebra

The Scalar Product

Symmetries

Maps

Symmetries of the Square

Combining Symmetries

Groups

Groups of Small Order

Symmetry Groups of Regular Polygons

Symmetries as Permutations

Fields

The Real Numbers

Absolute Value

Useful Inequalities

Standard Functions

Trigonometric Functions

Back to Vectors

Exercises on Vectors

Exercises on Symmetries and Groups

Exercises on Fields and Real Functions

Check Yourself

Recurrences

The Tower of Hanoi

Closed Forms

Lines in the Plane

Linear Recurrences

Inhomogeneous Recurrences

The Josephus Problem

Reading the Answer in Binary

The Repertoire Method

Radix Notation

Representation in a Base

Sums

Sequences

Sigma Notation

Iverson Brackets

Geometric Sums

Sums and Recurrences

The Summation Factor

Exercises on Recurrences

Exercises on Sums

Check Yourself

Imperative Knowledge and Computation

Computability

Syntax and Semantics

Problems, Words and Languages

Pseudocode

Objects and Types

Expressions and Relational Operators

Arithmetic Operators

Logical Operators

The Operators in One Place

Variables and State

Names and Comments

Multiple Assignment

Numbers in Other Bases

Branching

Conditional Statements

Nested Conditionals

Compound Tests and Updating State

Conditional Expressions

Constant Time

Iteration

The While Loop

Leaving a Loop Early

The For Loop

The Range Function

Reassigning the Loop Variable

Iterating Over a String

Nested Loops

Continue and Pass

Divisibility and Primality

Trial Division to the Square Root

Searching for the nnnth Object

Digits in an Arbitrary Base

Running Time

Landau Notation

The Cost of Schoolbook Arithmetic

Searching for the $n$ th Object