Counting Operations

Why Not Just Time It

Two Algorithms, One Same Result

There are almost always several ways to solve the same problem. They give the same result, but not at the same cost. How can we objectively compare two algorithms?

The temptation is to time them. But the time measured in seconds depends on the machine, the language, what else the computer is doing at the same time, the processor's temperature... A slow algorithm on an old phone can seem fast on a recent server. The stopwatch doesn't measure the algorithm, it measures a context.

The Idea: Count Operations, Not Seconds

Instead, we prefer to count the number of elementary operations the algorithm performs, as a function of the input size, denoted n. This number does not depend on the machine or the language: it is intrinsic to the algorithm.

def somme(liste):
    total = 0              # (1 operation)
    for x in liste:        # (the loop runs n times)
        total += x         # (1 operation, repeated n times)
    return total           # (1 operation)

For a list of size n, this algorithm performs about 1 + n + 1 = n + 2 operations. What matters is the term that grows with n: the n.

What Matters Is How It Grows

The point is not to calculate an exact number, but to know how the cost evolves as n increases. If you double the size of the input, does the time double? Is it multiplied by four? Does it stay constant?

   Algorithm A: ~ n operations       (double n  ->  double the cost)
   Algorithm B: ~ n^2 operations     (double n  ->  x4 the cost)

For n = 10, A does 10 operations and B does 100 — not dramatic. But for n = 1 000 000, A does a million and B does a trillion. The difference is no longer a matter of machine: it is structural.

The Worst Case

As a precaution, we generally reason about the worst case: the scenario where the algorithm works the hardest. Searching for an element in a list might succeed on the very first try (luck) or require scanning the whole thing (element absent). It's this latter scenario, the worst case, that gives a reliable guarantee.

In Summary