Counting steps: input size and cost models

A timing tells you how long a program took on one computer, once. A count of its steps tells you something that holds on every computer: how the work grows when the input grows. This lesson counts steps exactly, the way later lessons and written exams need, before the next lesson simplifies the counts into Big-O notation.

What to count

Two choices come first.

• The input size, n. It is whatever grows. For a list it is the number of items; for a graph, the number of vertices and edges (two sizes, V and E); for two lists, both lengths. For a single number it is the number of its digits or bits, not the number itself: a whole number in Python can have any number of digits, and adding two numbers of a million digits each means handling every one of those digits.
• The basic operation. It is the step that repeats most, and whose count decides the total: comparisons when searching or sorting, additions when summing, the innermost line of a loop nest.

The cost model says what one step costs. The usual one charges one unit for each basic operation on numbers of a fixed size, and ignores the difference between, say, an addition and a comparison. That is coarse, and deliberately so: it makes counts comparable, and the constant factors it ignores are what timing measures. The CS2023 curriculum lists input size and primitive operations as part of its framework for complexity analysis.

Loops: add, multiply, sum

Four rules cover most loop nests.

• One after the other, add. A loop of n steps followed by another of n steps makes 2n.

• One inside the other, multiply. If the inner loop runs m times for each of the n outer passes, the inner line runs n × m times.

• An inner loop that depends on the outer one, sum. If the inner loop runs i times on pass i, add up 0 + 1 + … + (n − 1):

  $$\sum_{i=0}^{n-1} i = \frac{n(n-1)}{2}$$

• A loop that halves, count the halvings. while n > 0: n //= 2 runs once for each binary digit of n, which is ⌊log₂ n⌋ + 1 times for n ≥ 1. Python’s int.bit_length() gives exactly that number.

This program runs each kind of loop with a counter inside it and checks every count against its formula:

def one_loop(n):
    count = 0
    for i in range(n):
        count += 1
    return count


def two_nested(n):
    count = 0
    for i in range(n):
        for j in range(n):
            count += 1
    return count


def triangle(n):
    count = 0
    for i in range(n):
        for j in range(i):  # the inner loop runs 0, 1, 2, ..., n - 1 times
            count += 1
    return count


def halving(n):
    count = 0
    while n > 0:
        n //= 2
        count += 1
    return count


print(f"{'n':>6} {'one loop':>9} {'two nested':>11} {'triangle':>9} {'halving':>8}")
for n in (1, 2, 10, 100, 1000):
    counts = one_loop(n), two_nested(n), triangle(n), halving(n)
    assert counts == (n, n * n, n * (n - 1) // 2, n.bit_length())
    print(f"{n:>6,} {counts[0]:>9,} {counts[1]:>11,} {counts[2]:>9,} {counts[3]:>8,}")
print("Every count equals n, n squared, n(n - 1)/2 and the bit length of n.")

     n  one loop  two nested  triangle  halving
     1         1           1         0        1
     2         2           4         1        2
    10        10         100        45        4
   100       100      10,000     4,950        7
 1,000     1,000   1,000,000   499,500       10
Every count equals n, n squared, n(n - 1)/2 and the bit length of n.

function oneLoop(n) {
  let count = 0;
  for (let i = 0; i < n; i++) count++;
  return count;
}

function twoNested(n) {
  let count = 0;
  for (let i = 0; i < n; i++) for (let j = 0; j < n; j++) count++;
  return count;
}

function triangle(n) {
  let count = 0;
  for (let i = 0; i < n; i++) for (let j = 0; j < i; j++) count++; // the inner loop runs 0, 1, ..., n - 1 times
  return count;
}

function halving(n) {
  let count = 0;
  while (n > 0) {
    n = Math.floor(n / 2);
    count++;
  }
  return count;
}

const bitLength = (n) => 32 - Math.clz32(n); // for 0 <= n < 2 ** 32
const fmt = (x, width) => String(x).replace(/\B(?=(\d{3})+$)/g, ',').padStart(width); // 1000000 -> 1,000,000
console.log(`${'n'.padStart(6)} ${'one loop'.padStart(9)} ${'two nested'.padStart(11)} ${'triangle'.padStart(9)} ${'halving'.padStart(8)}`);
for (const n of [1, 2, 10, 100, 1000]) {
  const counts = [oneLoop(n), twoNested(n), triangle(n), halving(n)];
  const formulas = [n, n * n, (n * (n - 1)) / 2, bitLength(n)];
  if (counts.some((c, k) => c !== formulas[k])) throw new Error(`a count differs from its formula for n = ${n}`);
  console.log(`${fmt(n, 6)} ${fmt(counts[0], 9)} ${fmt(counts[1], 11)} ${fmt(counts[2], 9)} ${fmt(counts[3], 8)}`);
}
console.log('Every count equals n, n squared, n(n - 1)/2 and the bit length of n.');

     n  one loop  two nested  triangle  halving
     1         1           1         0        1
     2         2           4         1        2
    10        10         100        45        4
   100       100      10,000     4,950        7
 1,000     1,000   1,000,000   499,500       10
Every count equals n, n squared, n(n - 1)/2 and the bit length of n.

Read down a column to see the growth. Going from n = 100 to n = 1,000 multiplies one loop’s count by 10, the nested loops’ count by 100 and the triangle’s by about 100, while the halving loop needs only three more steps.

Best, worst and average cases

Some algorithms take a different number of steps on different inputs of the same size. Linear search compares the key with each item in turn until it finds it:

from fractions import Fraction


def linear_search(items, key):
    """Position of key in items (or -1), and how many comparisons it took to find out."""
    comparisons = 0
    for i, item in enumerate(items):
        comparisons += 1
        if item == key:
            return i, comparisons
    return -1, comparisons


for n in (1, 5, 10, 1000):
    items = list(range(n))
    found = [linear_search(items, key)[1] for key in items]  # every position in turn
    absent = linear_search(items, -1)[1]
    average = Fraction(sum(found), n)
    assert average == Fraction(n + 1, 2)
    print(f"n = {n:>4}: best {min(found)}, worst {max(found)}, missing key {absent}, average {average}")

n =    1: best 1, worst 1, missing key 1, average 1
n =    5: best 1, worst 5, missing key 5, average 3
n =   10: best 1, worst 10, missing key 10, average 11/2
n = 1000: best 1, worst 1000, missing key 1000, average 1001/2

• The best case is the input that needs the fewest steps: the key is the first item, 1 comparison.
• The worst case is the input that needs the most: the key is the last item, or not there at all, n comparisons.
• The average case is the mean over a stated set of inputs. If the key is present and every position is equally likely, the average is (1 + 2 + … + n) / n = (n + 1) / 2 comparisons, which the program computes exactly with fractions.Fraction.

The average depends on its assumption. If the key is missing half the time, the average is higher; if users search mostly for the first few items, it is lower. Say which inputs you average over, or the number means nothing. The worst case needs no assumption, which is why guarantees are usually stated for it.

Work hidden in one line

A single line of Python can hide a loop. To make such loops visible, this program uses Probe, a number that counts every time Python compares it with another:

import random


class Probe:
    """A number that counts how often Python compares it with another."""

    comparisons = 0

    def __init__(self, value):
        self.value = value

    def __eq__(self, other):
        Probe.comparisons += 1
        return self.value == other.value

    def __lt__(self, other):
        Probe.comparisons += 1
        return self.value < other.value


def count(label, action):
    Probe.comparisons = 0
    action()
    print(f"{label:<30} {Probe.comparisons:>8,} comparisons")


items = [Probe(v) for v in range(10_000)]
shuffled = items[:]
random.Random(5).shuffle(shuffled)

count("Probe(9_999) in items", lambda: Probe(9_999) in items)
count("Probe(-1) in items", lambda: Probe(-1) in items)
count("items.index(Probe(5_000))", lambda: items.index(Probe(5_000)))
count("items.count(Probe(7))", lambda: items.count(Probe(7)))
count("max(items)", lambda: max(items))
count("sorted(items), already sorted", lambda: sorted(items))
count("sorted(shuffled)", lambda: sorted(shuffled))

Probe(9_999) in items            10,000 comparisons
Probe(-1) in items               10,000 comparisons
items.index(Probe(5_000))         5,001 comparisons
items.count(Probe(7))            10,000 comparisons
max(items)                        9,999 comparisons
sorted(items), already sorted     9,999 comparisons
sorted(shuffled)                120,222 comparisons

x in items compares x with the items one by one until it finds it, so a missing item costs a comparison with every item. items.index(x) stops at the first match; items.count(x) never stops early. max() compares each item with the best so far. sorted() notices that sorted input is already in order and makes only n − 1 comparisons, but on shuffled input it made about 120,000, a little under n log₂ n. Python’s documentation lists the costs of the common operations on its built-in types, and these are the ones that most often hide inside a loop:

The danger is a hidden loop inside a visible one. for x in a: if x in b: … looks like one pass, but each in on a list b scans b, so the line runs up to len(a) × len(b) comparisons. Turning b into a set first makes each lookup take about the same time however large b is.

The cost of pop(0) is easy to see in a measurement. Emptying a list from the front moves the remaining items once per removal, about n²/2 moves in all, while a deque removes from its front without moving anything:

import time
from collections import deque


def empty_list(n):
    items = list(range(n))
    while items:
        items.pop(0)  # removes the first item: every other item moves one place


def empty_deque(n):
    items = deque(range(n))
    while items:
        items.popleft()


def fastest_ms(function, n, repeats=5):
    """The least CPU time of several runs: time.process_time() counts only this program's own work."""
    best = float("inf")
    for _ in range(repeats):
        start = time.process_time()
        function(n)
        best = min(best, time.process_time() - start)
    return best * 1000


print(f"{'n':>7} {'list.pop(0)':>12} {'deque.popleft()':>16} {'ratio':>7}")
for n in (10_000, 20_000, 40_000):
    slow, quick = fastest_ms(empty_list, n), fastest_ms(empty_deque, n)
    print(f"{n:>7,} {slow:>9.1f} ms {quick:>13.2f} ms {slow / quick:>6.0f}x")

      n  list.pop(0)  deque.popleft()   ratio
 10,000       6.9 ms          0.24 ms     28x
 20,000      33.9 ms          0.49 ms     69x
 40,000     143.4 ms          1.01 ms    141x

Each doubling of n multiplies the time of pop(0) by four or more, and that of popleft() by about two, so the gap keeps growing. The program uses time.process_time(), which counts only the processor time of this program, so other programs running at the same moment disturb the measurement less than they disturb a wall clock.

Strings have the same trap. Each s + t builds a new string, so building a long string by adding pieces in a loop can cost time proportional to the square of its final length: Python’s documentation calls the cost of repeated concatenation quadratic. CPython can often extend the string in place instead, so a quick test may look fast, but PEP 8 warns that this optimisation is fragile even in CPython, and implementations without reference counting do not have it. The documentation’s advice holds everywhere: collect the pieces in a list and join them once with "".join(pieces).

Key takeaways

• Choose the input size (what grows) and the basic operation (what repeats most) before counting anything.
• Loops in sequence add, nested loops multiply, a dependent inner loop sums (0 + 1 + … + (n − 1) = n(n − 1)/2) and a halving loop runs ⌊log₂ n⌋ + 1 times.
• Best, worst and average cases are different functions of n; an average needs a stated assumption about the inputs.
• in on a list, index, count, max, slicing, pop(0), insert(0, x) and string concatenation all take time that grows with n, even though each fits on one line.