Counting Steps Instead of Seconds

7.1The problem with seconds

Last week you measured seconds, and seconds were useful. But they carry passengers. A time of 0.04 s describes:

• the algorithm — the thing you actually care about;
• the machine — a 2015 laptop or a 2026 server;
• the language — Python is far slower than C for the same steps;
• the moment — what else was running, whether the cache was warm.

Publish "0.04 seconds" and it is obsolete when you upgrade your laptop. Publish "one step per item in the list" and it is true forever, on every machine, in every language. That is why the field settled on counting steps as the primary description and uses timing as supporting evidence.

7.2T(n): the step-count formula

T(n) is simply "how many steps this code takes when the input size is n". We count assignments — the cost of storing one value — as an explicit teaching cost model. Check that omitted work is bounded per iteration before using this count to describe overall growth.

def sum_to(n):
    total = 0                          # 1 assignment
    for number in range(1, n + 1):     # n assignments to 'number'
        total = total + number         # n assignments to 'total'
    return total

So T(n) = 1 + 2n. For n = 10 that is 21 steps; for n = 1 000, 2 001; for n = 1 000 000, 2 000 001.

Now the formula version of the same job:

def sum_formula(n):
    return n * (n + 1) // 2            # a fixed handful of operations

If we count each arithmetic operation as one step, this expression uses a fixed number of arithmetic operations. Python integers can grow in bit length, so actual arithmetic cost is not constant for arbitrarily large integers. That single fact — the formula's step count does not contain n — is exactly what you saw in week 5, when its timings refused to grow.

7.3The dominant term

Real formulas are messier. Suppose you carefully count a piece of code and get:

T(n) = 5n² + 200n + 3000

Which part matters? Put numbers in and watch:

For small inputs the constant 3 000 can dominate, and such inputs may matter in practice. As n grows, the n² term dominates this polynomial: the relative shares of the linear and constant terms approach zero.

So we throw away the small stuff and keep the shape:

7.4Why dropping the 5 is honest

It feels like cheating. It is not, and the reason is worth a moment. Compare two methods:

• Method A: T(n) = 100n — clumsy, a hundred steps per item.
• Method B: T(n) = n² — tidy, but nested.

At n = 50, A costs 5 000 and B costs 2 500: B wins. At n = 100 they tie at 10 000. At n = 1 000, A costs 100 000 and B costs 1 000 000 — A wins by ten times. At n = 100 000, A wins by a factor of a thousand.

A constant factor buys you a fixed head start; a better growth pattern eventually wins by any margin you like. Buying a computer twice as fast halves your constant — and moves the crossover a little. Choosing a better algorithm changes the shape of the curve, and that is the only thing that survives more data.

7.5Which operation do you count?

A fair question hangs over §7.2: we chose to count assignments, but why those? A loop also does comparisons, additions, and list look-ups. Would counting a different one change the answer?

Take a linear search and count the thing that actually does the work — the comparison item == target:

def contains(data, target):
    comparisons = 0
    for item in data:
        comparisons += 1
        if item == target:
            return True, comparisons
    return False, comparisons

haystack = list(range(1000))
print(contains(haystack, 999))   # found at the very end
print(contains(haystack, -1))    # missing: full pass

In the worst case (target missing, or last) the loop makes n comparisons — so counting comparisons gives T(n) = n. Counting assignments to item would also give n. Counting the loop's additions: also n. Every reasonable choice lands on "some constant times n", so the dominant term — the part we keep — is n whichever operation you picked.

This is also why the constant is machine-dependent and the shape is not. On a fast CPU a comparison might take 2 nanoseconds; on a slow one, 20. In C it is faster than in Python. Every one of those facts scales the constant up or down — none of them turns an n into an n². The growth pattern is a property of the algorithm; the constant is a property of everything else.

7.6Arithmetic growth vs geometric growth

There is one more distinction that decides an algorithm's class, and it hides in how a loop variable changes. Watch two loops that both stop at n:

def arithmetic_steps(n):     # i goes 0, 1, 2, 3, ... up to n
    steps = 0
    i = 0
    while i < n:
        i = i + 1            # ADD a constant each pass
        steps += 1
    return steps

def geometric_steps(n):      # i goes n, n/2, n/4, ... down to 1
    steps = 0
    i = n
    while i > 1:
        i = i // 2           # MULTIPLY (by 1/2) each pass
        steps += 1
    return steps

for n in [8, 1024, 1000000]:
    print(f"n={n:>8}   adding: {arithmetic_steps(n):>8}   halving: {geometric_steps(n)}")

The gap is enormous, and it comes entirely from add versus multiply. When a loop variable adds a fixed amount, it needs about n passes to reach n — that is arithmetic growth, and it gives O(n). When a loop variable multiplies (here, halves) each pass, it reaches its target in only about log₂ n passes — geometric growth, and it gives O(log n). Doubling n adds exactly one pass to the halving loop, which is the "small fixed addition, not a multiple" row you spotted in last week's ratio table.

A second dominant-term example: the triangular loop

Nested loops are not always a clean n². Here the inner loop's length depends on the outer counter:

def triangular(n):
    count = 0
    for i in range(n):
        for j in range(i):       # runs i times, not n
            count += 1
    return count

The inner loop runs 0 times, then 1, then 2, … up to n−1. Add those up:

T(n) = 0 + 1 + 2 + … + (n−1) = n(n−1)/2 = ½n² − ½n  →  keep n²

Only half the full grid of n² is visited, yet the dominant term is still n²: the ½ is a constant multiplier, and we drop it. So this loop is O(n²) and its ratio column will still read ≈ 4 when you double n — exactly the behaviour you will meet again in week 9's "checking off" anagram solution. Half of a quadratic is still a quadratic.

7.12The RAM model — counting the way computer scientists do

You have been counting steps all week without asking a slightly awkward question: what exactly is a step? Adding two numbers, comparing two letters, reading data[i] out of a list — are those all one step, or does a big multiplication cost more than a small one? The computer scientist Steven Skiena answers this with a deliberately simple picture called the Random Access Machine, or RAM model, and it is the quiet foundation under everything in this course.

The idea is a bargain. We agree to pretend that every simple operation costs exactly one time unit, and that this one unit is the same no matter what the values are. On this imaginary machine:

• arithmetic — +, −, ×, a division — is one step each;
• an assignment = is one step;
• a comparison such as a < b or x == y is one step;
• reading or writing one array slot, data[i], is one step — the "random access" part, meaning any slot is reachable in the same single unit, whether it is the first or the millionth;
• the bookkeeping of a function call — the one step of handing control over — counts too.

Once we accept that, the running time of a program is just the total number of those steps it performs. That is the whole model. It is exactly the number your step counters have been printing: a program that runs a one-step body n times costs n, and one that runs it n² times costs n². Counting assignments in §7.2 was a first, honest instance of RAM-model counting — we simply picked one operation and tallied it.

Is this true? Not literally. On a real chip a multiply can take longer than an addition, a value already in cache is fetched far faster than one out in main memory, and a number too big to fit a machine word costs more still. The RAM model wilfully ignores all of that. It is a simplification, and a proud one — the same kind of move a physicist makes when they drop air resistance to see the shape of a falling body. What we buy with the simplification is enormous: we can compare two algorithms with pencil and paper, on no particular machine, in no particular language, and get an answer that stays true when the hardware is replaced. That is the machine independence you met in §7.1, now given a name and a rule.

7.10Optional Studio Extension

7.11Words from this week

7.13Chapter problem set — Skiena 2.10

Here are four classic exercises from Skiena's The Algorithm Design Manual, worked at our level. Three of them are little loop puzzles written in pseudocode; for each we will first rewrite the loops as readable Python — so you can drop them into a notebook and run them — then trace what they count and read off the growth. The fourth is about counting the real work inside a familiar formula. Reach for the same tools you have used all week: the RAM-model step count, the dominant term, and a Python counter to check the arithmetic.

def mystery(n):
    r = 0
    for i in range(1, n):              # i = 1 .. n-1
        for j in range(i + 1, n + 1):  # j = i+1 .. n
            for k in range(1, j + 1):  # k = 1 .. j
                r += 1
    return r

prev = None
for n in [5, 10, 20]:
    r = mystery(n)
    ratio = "-" if prev is None else f"{r / prev:.2f}x"
    print(f"n={n:>3}   r={r:>6}   ratio {ratio}")
    prev = r

def pesky(n):
    r = 0
    for i in range(1, n + 1):          # i = 1 .. n
        for j in range(1, i + 1):      # j = 1 .. i
            for k in range(j, i + j + 1):  # k = j .. i+j
                r += 1
    return r

for n in [5, 10, 20]:
    r = pesky(n)
    formula = n * (n + 1) * (n + 2) // 3
    print(f"n={n:>3}   r={r:>5}   n(n+1)(n+2)/3={formula:>5}")

def foobar(n):
    for i in range(1, n // 2 + 1):     # i = 1 .. n/2
        for j in range(i, n - i + 1):  # j = i .. n-i
            for k in range(1, j + 1):  # k = 1 .. j
                print("foobar")

def foobar_count(n):
    total = 0
    for i in range(1, n // 2 + 1):
        for j in range(i, n - i + 1):
            for k in range(1, j + 1):
                total += 1             # one 'print' would fire here
    return total

prev = None
for n in [10, 20, 40]:
    t = foobar_count(n)
    ratio = "-" if prev is None else f"{t / prev:.1f}x"
    print(f"n={n:>3}   prints={t:>5}   ratio {ratio}")
    prev = t

T(n) = Σ [ (2m-i)(2m-i+1) - (i-1)i ] / 2   (i = 1..m, n = 2m)
     = Σ m(2m - 2i + 1)
       # numerator simplifies to 2m(2m - 2i + 1)
     = m [ (2m-1) + (2m-3) + ... + 1 ]
       # the odd numbers 1 .. 2m-1
     = m · m2 = m3 = (n/2)3 = n3/8
       # the first m odd numbers sum to m^2

def evaluate_naive(a, x):
    # a is the list of coefficients: a[0], a[1], ..., a[n]
    n = len(a) - 1
    p = a[0]
    xpower = 1
    for i in range(1, n + 1):
        xpower = x * xpower            # one multiplication
        p = p + a[i] * xpower          # one multiplication, one addition
    return p

def evaluate_horner(a, x):
    n = len(a) - 1
    p = a[n]                           # start from the top coefficient
    for i in range(n - 1, -1, -1):     # i = n-1, n-2, ..., 0
        p = p * x + a[i]               # one multiplication, one addition
    return p

def naive_counts(a, x):
    n = len(a) - 1; m = adds = 0; p = a[0]; xpower = 1
    for i in range(1, n + 1):
        xpower = x * xpower;      m += 1
        p = p + a[i] * xpower;    m += 1; adds += 1
    return p, m, adds

def horner_counts(a, x):
    n = len(a) - 1; m = adds = 0; p = a[n]
    for i in range(n - 1, -1, -1):
        p = p * x + a[i];         m += 1; adds += 1
    return p, m, adds

a = [2, -3, 1, 4]                # 2 - 3x + x^2 + 4x^3, so n = 3
print("naive :", naive_counts(a, 2))    # (value, mults, adds)
print("horner:", horner_counts(a, 2))