The cost of an algorithm

Counting operations

The second question

The lessons Designing correct loops and Recursion taught how to prove that an algorithm is correct: that it terminates and that its result satisfies the postcondition. Now, the lesson Numerical algorithms showed two equally correct primality tests, one with about $n$ divisions and the other with about $\sqrt{n}$, and the lesson Recursion, two correct ways of computing $F_{30}$, one with $2\,692\,537$ calls and the other with 29 additions. If this is so, correctness is not enough to choose: of two correct algorithms, one may answer in an instant and the other may not finish before the answer has stopped mattering. The second question asked of an algorithm is, therefore, how much it costs.

Cost could be measured with a clock, and the fourth section will do so. But the time of one run depends on the machine, on the compiler, on its options and on whatever else the computer is doing at the same time; nothing follows from it about the algorithm on another machine. What depends on none of that is the number of steps the algorithm takes. From this follows the first decision of this lesson: measure cost by counting, and leave the clock for checking the count.

Size and the dominant operation

Counting every step (each addition, each comparison, each increment of the index, each memory access) would be tedious and useless, because almost all of them accompany a main one in a fixed proportion. One therefore chooses the dominant operation: the one executed at least as many times as any other, up to a constant factor, and which for that reason represents them all. In summing the elements of a vector it is the addition; in finding a maximum, the comparison; in a primality test, the division. The number of times it is executed is expressed as a function of the input size, which is called $n$: the number of elements of the vector, the number being tested, the number of digits.

A simple loop that traverses a vector of $n$ elements and does a fixed amount of work with each one executes its dominant operation $n$ times. The maximum of a nonempty vector, on the other hand, starts with the first element as candidate and compares each of the others: $n - 1$ comparisons. The difference between $n$ and $n - 1$ is real but, as the third section will show, it changes nothing that matters.

The worst case

Some algorithms do not always execute the same number of operations on data of the same size. Searching for a value in a vector, traversing it until the value is found, takes a single comparison if the value is in the first position and $n$ if it is absent. To speak of its cost one of the two situations is chosen, and the usual choice is the worst case: the maximum number of operations over all inputs of size $n$. The reason is the same one for which a contract is written for all the inputs that satisfy the precondition: the worst case is a guarantee, and the best case, a hope. So linear search costs $n$ comparisons in the worst case, and when this lesson says “the cost” without qualification, it means the cost in the worst case.

Nested loops

The lesson Loops taught how to count the iterations of two nested loops. If the inner loop always makes $m$ iterations for each of the $n$ of the outer loop, the inner body is executed $n \cdot m$ times. If the inner loop depends on the outer one, one adds row by row. The case that comes up most often when working with collections is that of all pairs: comparing each element with each of those that follow it, as when checking whether a vector has duplicates.

#include <print>​int main(){    for (int n{10}; n <= 10'000; n *= 10) {        long long comparisons{0};        for (int i{0}; i < n; ++i) {            for (int j{i + 1}; j < n; ++j) {                ++comparisons;            }        }        std::println("n = {:>6}: {:>10} comparisons; n(n - 1)/2 = {}",                     n, comparisons, static_cast<long long>(n) * (n - 1) / 2);    }}

n =     10:         45 comparisons; n(n - 1)/2 = 45n =    100:       4950 comparisons; n(n - 1)/2 = 4950n =   1000:     499500 comparisons; n(n - 1)/2 = 499500n =  10000:   49995000 comparisons; n(n - 1)/2 = 49995000

The counter stands in for the comparison that the real algorithm would make. In iteration $i$ of the outer loop, the inner one goes from $i + 1$ to $n - 1$ and makes $n - 1 - i$ iterations; so the total is $(n - 1) + (n - 2) + \cdots + 1 + 0$, the sum from the lesson Loops:

The output confirms the formula for each size. The counter is long long because from $n$ of about sixty-five thousand onward the number of pairs exceeds the maximum of int (32 bits on this platform), and the formula multiplies after converting for the same reason: the counter of a quadratic algorithm overflows long before the data do.

Notice already what the third section will generalize: when $n$ is multiplied by 10, the comparisons are multiplied by about 100. With ten items, 45 comparisons; with ten thousand, almost fifty million.