In the previous topic we learned to measure time. But seconds depend on the machine. In this topic we learn to compare algorithms independently of it.

The problem with seconds

Measured time depends on the processor, Python version, load and caches. The same code may take 2 seconds on a laptop and 0.5 seconds on a server, yet the algorithm is the same. We need the number of elementary operations as a function of the input size n.

Operation counts of linear and quadratic algorithms
Operation counts of linear and quadratic algorithms

The model

  • Input size n: list length, number of characters in a string, number of vertices and edges in a graph.
  • Elementary operation: assignment, comparison, arithmetic, indexing; each is one step.
  • f(n): the number of steps of an algorithm. We care about its growth character.

With nested loops the steps multiply:

python
def count_linear(n):
    ops = 0
    for _ in range(n):
        ops += 1
    return ops