Computer Science › Section F · Algorithms › Topic F.6
Efficiency and correctness
Two questions decide whether an algorithm is any good: how its running time grows as the input grows, and whether it really does what it claims for every input. This topic shows how to count steps, classify growth with big-theta notation, and prove a loop correct with an invariant.
Why efficiency still matters
Computers carry out billions of instructions a second, yet the choice of algorithm can still decide whether a task takes a blink or an afternoon. Algorithm analysis studies the resources an algorithm needs, mainly time and memory. Rather than timing one program on one machine, we count how often the main operation, such as a comparison, is performed, as a function of the input size n, and ask how that count grows as n grows. Memory is measured the same way, as space complexity: insertion sort needs a fixed amount of extra memory; merge sort needs extra room growing with n.
Worked example: searching 50,000 records
A library keeps 50,000 member records sorted by ID number, and checking one record takes 5 milliseconds. 1. Sequential search: with no idea where a given ID lies, the average search checks about half the list, 25,000 records. 2. Time: 25,000 × 5 ms = 125 seconds, over two minutes per lookup. 3. Binary search: at most \(\lfloor \log_2 50000 \rfloor + 1 = 16\) records, as "Recursive structures: binary search" showed. 4. Time: 16 × 5 ms = 0.08 seconds. 5. Note the kinds of analysis: step 1 is an average case, step 3 a worst case. On the same data and computer, the algorithm alone made the difference.
Best, worst and average cases
The work an algorithm does often depends on the particular input, not just its size. The best case is the least work for any input of size n, the worst case the most, and the average case the typical amount over many inputs. Sequential search has a best case of 1 comparison (the target is first) and a worst case of n (the target is last or absent). Worst-case figures are the most common, because they give a guarantee; average-case figures need an assumption about which inputs are likely.
Analysing insertion sort
Count comparisons in "Iterative structures: sequential search and insertion sort". Best case, an already sorted list: each of the n - 1 passes makes one comparison, so n - 1 in all. Worst case, a list in reverse order: the Key for position 2 is compared with 1 entry, the next with 2, and so on up to n - 1, giving
For 10 entries that is 45 comparisons, and for 1,000 entries 499,500. On average each Key travels about half way back through the sorted part, so for large n the count is roughly \(\frac{n^2}{4}\), half the worst case.
Growth rates and big-theta notation
What matters for large inputs is the shape of the growth, not the exact formula. Constant factors and slower-growing terms are dropped: \(3n^2 + 5n + 2\) and \(\frac{n(n-1)}{2}\) both grow like \(n^2\), so both are in the class \(\Theta(n^2)\), read "big theta of n squared". Insertion sort's worst case is \(\Theta(n^2)\), sequential search's is \(\Theta(n)\), and binary search's is \(\Theta(\log n)\). Related notations: big O gives an upper bound (grows no faster than) and big omega, \(\Omega\), a lower bound; \(\Theta\) means both at once. A useful consequence: for a \(\Theta(n^2)\) algorithm, ten times the input means about a hundred times the work.
Comparing the classes
From slowest-growing to fastest: \(\Theta(1)\), \(\Theta(\log n)\), \(\Theta(n)\), \(\Theta(n \log n)\), \(\Theta(n^2)\), \(\Theta(2^n)\) and \(\Theta(n!)\). At n = 1,000, \(\log_2 n\) is about 10, \(n \log_2 n\) about 10,000, \(n^2\) a million, and \(2^n\) has 302 digits. Rough rules for reading pseudocode: one loop over n entries suggests \(\Theta(n)\); a loop nested inside another, each over n, suggests \(\Theta(n^2)\); halving the problem each step suggests \(\Theta(\log n)\); steps done one after another add, and the fastest-growing one dominates. It is proved that any sort working only by comparing entries needs on the order of \(n \log_2 n\) comparisons in its worst case, a bound merge sort meets.
Correct, or only believed correct?
A program that seems right can still be wrong. Suppose a function finds the largest entry by starting with Big = 0 and replacing Big whenever an entry is larger. It passes tests on [3, 8, 5], [0, 7, 2] and [9, 9, 9]. Yet on [-4, -9, -2] it returns 0, a number not even in the list, because no entry beats the starting value. Testing shows only that a program works on the cases tried; any wider conclusion is a guess. Proving correctness means reasoning about every input the program is meant to handle, which is what program verification aims to do.
Preconditions, postconditions and assertions
A proof of correctness starts from preconditions, the conditions assumed true when the program begins, such as "the list has at least one entry". Its goal is the postcondition, the promised result, such as "Big equals the largest entry". In between, you establish assertions, statements known to be true at particular points. Simple rules carry them through the code. After X = Y, anything true of Y is true of X. Inside if (C):, both the earlier assertions and C hold; inside the else, the earlier assertions and not C hold. If the assertion reached at the end matches the postcondition, the program is correct.
Loop invariants
Loops need one more tool. A loop invariant is an assertion that is true every time the loop's test is reached. To use one, show three things: it holds when the loop first starts; if it holds before a pass, it still holds after; and the invariant together with the termination condition implies the postcondition. Then argue separately that the loop actually ends. Insertion sort's outer loop has the invariant "positions 1 to N - 1 are sorted"; it stops when N exceeds length(L), so all positions are sorted. Some languages, such as SPARK, which is based on Ada, let programmers write these assertions into the code so tools can check them.
Worked example: proving a loop correct
Precondition: L has at least one entry.
Invariant: Big is the largest of L[1] to L[K]. 1. At the start K = 1 and Big = L[1], so it holds. 2. In a pass, K grows by one and Big is replaced only if the new entry is larger, so Big is again the largest of L[1] to L[K]. 3. The loop stops when K = length(L), so Big is the largest of the whole list. 4. K rises by 1 each pass towards length(L), so the loop ends. On [-4, -9, -2] it correctly returns -2.
Common mistakes to avoid
First, keeping constants or lower terms in the class: \(\Theta(3n^2 + 5n)\) is just \(\Theta(n^2)\). Second, assuming twice the input means twice the time for every algorithm; for \(\Theta(n^2)\) it is four times. Third, comparing a worst case for one algorithm with a best case for another. Fourth, treating passing tests as proof: Big = 0 passed three tests and was still wrong. Fifth, stating an invariant but never showing that the loop ends.
Key takeaways
Efficiency is measured by how the count of a main operation grows with input size n, in best, worst and average cases. Insertion sort needs n - 1 comparisons at best and n(n - 1)/2 at worst. Big-theta drops constants and slower terms, giving classes from Θ(1) and Θ(log n) up to Θ(2ⁿ) and Θ(n!); big O is an upper bound and big omega a lower one. Testing cannot prove correctness. A proof runs from preconditions through assertions to postconditions, and a loop invariant plus the termination condition gives the result, provided the loop ends.
Flashcards
Flashcard
The study of the time and memory an algorithm needs
Test your understanding
Question 1 of 5
In its worst case, how many comparisons does insertion sort make on a list of 20 entries?
Question 2 of 5
An algorithm makes 6n³ + 2n² + 50 steps on an input of size n. Which class is it in?
Question 3 of 5
A Θ(n²) algorithm takes 2 seconds on 1,000 items. About how long should it take on 10,000 items?
Question 4 of 5
When the loop in FindLargest stops, what lets us conclude that Big is the largest entry in the list?
Question 5 of 5
A largest-entry function starts with Big = 0. Which test input exposes its bug?
