The Lumenary · Grades 9–12

Algorithms, correctness and efficiency

Name: ______________________

Date: ______________________

You will learn to

Implement linear search, binary search and insertion sort, and trace them on examples
Prove an algorithm correct with a loop invariant and a decreasing measure, for binary search and for Euclid's algorithm
Prove that binary search on $n$ items makes at most $\lfloor \log_2 n \rfloor + 1$ comparisons, and that insertion sort makes at most $n(n-1)/2$
Prove that every comparison-based sorting method needs at least $\log_2(n!)$ comparisons in the worst case, which grows like $n \log_2 n$
Compare growth rates such as $\log n$ , $n$ , $n \log n$ , $n^2$ and $2^n$ , and explain why faster computers do not make efficiency irrelevant

1.
What is the largest number of comparisons binary search can make on a sorted list of $1000$ entries?
2.
How many comparisons does insertion sort make, in the worst case, to sort a list of $10$ entries?
3.
This loop adds up a list $a$ of length $n$ :
```
s = 0
for i in range(n):      # i = 0, 1, ..., n - 1
    s = s + a[i]
```
Which statement is a loop invariant that holds at the start of each pass (before $a_i$ is added) and proves that $s$ is the total at the end?
- A. $s = a_0 + a_1 + \dots + a_{i-1}$
- B. $s = a_0 + a_1 + \dots + a_i$
- C. $s \ge 0$
- D. $s = a_0 + a_1 + \dots + a_{n-1}$
4.
A classmate's sorting function passed $1000$ random tests on lists of up to $50$ numbers. Which statement is correct?
- A.This is evidence that the function works, but it does not prove it works on every list.
- B.It is now proved correct for all lists of length at most $50$ .
- C.It is proved correct, since $1000$ is a large number of tests.
- D.The tests are useless; only proofs matter.
5.
An algorithm takes $n^2$ steps on inputs of size $n$ . A new computer is $100$ times faster. In the time the old computer needed for size $n$ , the new one can handle size $k \cdot n$ . What is $k$ ?
6.
In the correctness proof of binary search, suppose $a_{mid} < t$ . Why may we discard the indices $lo, \dots, mid$ ?
- A.The list is sorted, so $a_i \le a_{mid} < t$ for every $i \le mid$ : none of these entries equals $t$ .
- B.Because $mid$ is the middle, so $t$ is equally likely to be in either half.
- C.Because we have already compared $t$ with all of $a_{lo}, \dots, a_{mid}$ .
- D.Because $lo \le mid \le hi$ .
7.
Let r := bsearch p lo hi. Which Lean proposition says that r is the first point where the test p gives true?
- A.p r = true ∧ ∀ k, k < r → p k = false
- B.p r = true
- C.∃ k, p k = true
- D.∀ k, k < r → p k = true
8.
Write binary_search(a, t) for a sorted list a. Return a pair (index, probes): an index i with a[i] == t (or -1 if t is absent), and the number of times you compared t with an entry of the list. The tests check correctness on many lists and that probes never exceeds $\lfloor \log_2 n \rfloor + 1$ , which is len(a).bit_length() in Python.
Computational — Practice
9.
Using the decision-tree argument (Theorem 6), what is the smallest number of comparisons that any comparison-based method could need, in the worst case, to sort $5$ different numbers?
10.
Run Euclid's algorithm on $(89, 55)$ . How many divisions with remainder does it perform before reaching a pair whose second number is $0$ ? (Count every step $(a, b) \to (b, a \bmod b)$ .)

Answer key — Algorithms, correctness and efficiency

1.
Since $2^9 = 512 \le 1000 < 2^{10}$ , $\lfloor \log_2 1000 \rfloor = 9$ , and binary search makes at most $9 + 1 = 10$ comparisons. The bound is attained, for example when the target is larger than every entry: the range shrinks $1000 \to 500 \to 250 \to 125 \to 62 \to 31 \to 15 \to 7 \to 3 \to 1 \to 0$ , ten comparisons.
2.
At most $1 + 2 + \dots + 9 = \frac{9 \cdot 10}{2} = 45$ comparisons, which is $\frac{n(n-1)}{2}$ with $n = 10$ . A list in decreasing order, such as $10, 9, \dots, 1$ , needs all $45$ : each new entry is smaller than everything before it.
3.
$s = a_0 + \dots + a_{i-1}$ . Initially ( $i = 0$ , $s = 0$ ) it holds, as the empty sum is $0$ . If it holds at the start of pass $i$ , then after s = s + a[i] we have $s = a_0 + \dots + a_i$ , which is the invariant for $i + 1$ . When the loop stops, $i = n$ , so $s = a_0 + \dots + a_{n-1}$ . This is a proof by induction on $i$ .
4.
Passing tests is experimental evidence. To know the function sorts every list you need a proof — for insertion sort, the invariant "the first $i$ entries are sorted" plus termination. Testing remains useful for finding mistakes, including mistakes in the proof's assumptions.
5.
We need $(kn)^2 = 100\,n^2$ , so $k^2 = 100$ and $k = 10$ . A hundredfold faster machine handles only ten times larger inputs for a quadratic algorithm — and for an exponential $2^n$ algorithm only about $\log_2 100 \approx 6.6$ more items.
6.
Because $a_0 \le a_1 \le \dots$ , every $a_i$ with $i \le mid$ satisfies $a_i \le a_{mid} < t$ , so $a_i \ne t$ . Hence if $t$ occurs at all, it occurs in $mid + 1, \dots, hi$ , and setting $lo = mid + 1$ preserves the invariant. On an unsorted list this step fails, and so does binary search.
7.
p r = true ∧ ∀ k, k < r → p k = false. A specification must say everything we want: option (b) is satisfied by a lazy algorithm that always answers hi. Writing precise specifications is half the work of proving programs correct.

def binary_search(a, t):
    lo, hi = 0, len(a) - 1
    probes = 0
    while lo <= hi:
        mid = (lo + hi) // 2
        probes += 1
        if a[mid] == t:
            return mid, probes
        elif a[mid] < t:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1, probes

The tests are evidence; Theorems 2 and 3 are the proof that this works, within $\lfloor \log_2 n \rfloor + 1$ probes, for every sorted list.

9.
A decision tree of height $h$ has at most $2^h$ leaves and must have at least $5! = 120$ . Since $2^6 = 64 < 120 \le 128 = 2^7$ , we need $h \ge 7$ . Remarkably, $7$ is also enough: a clever method (merge insertion, due to Ford and Johnson, 1959) sorts any 5 numbers in 7 comparisons. Our Lean file proves the lower half of this: five_items_need_seven.
10.
$(89, 55) \to (55, 34) \to (34, 21) \to (21, 13) \to (13, 8) \to (8, 5) \to (5, 3) \to (3, 2) \to (2, 1) \to (1, 0)$ : nine divisions, and $\gcd(89, 55) = 1$ . Every quotient but the last is $1$ , so the numbers shrink as slowly as possible — consecutive Fibonacci numbers are the worst case for Euclid (Lamé, 1844). Even so, $9$ steps is at most five times the number of digits of $55$ , as Lamé's theorem promises.