Counting Steps Instead of Seconds

The counter should match to within the one or two setup assignments you may have counted differently. That "off by one or two" is precisely the constant term the simplification rules tell you to discard.

n; n²; n³; a constant (does not grow); n log n — because n log n grows faster than n.

A crossover near n = 100, though the exact point wobbles with machine noise and Python overheads. The lesson is not the exact number: it is that the crossover exists, is predictable from the formulas, and that beyond it the gap only widens.

The raw counts differ by a constant factor (say n vs 3n), but both double when n doubles — the ratio column is identical. The choice of operation set the constant, not the shape, so either is fine as long as you state which you counted.

count equals n(n−1)/2 exactly: 124 750, 499 500, 1 999 000. The ratio is ≈ 4 because the dominant term is ½n² — doubling n multiplies ½n² by 4. The ½ is a constant we drop; half a quadratic is still a quadratic.

The adding loop's count multiplies by 1 000 each time (linear). The halving loop's count rises by only about 10 each time (log₂ 1000 ≈ 10) — that is O(log n). Doubling n adds exactly one step to the halving loop, which is precisely the logarithmic row of last week's ratio table.

Start from the inside and work out. The innermost loop runs k = 1 .. j, which is exactly j passes, and each pass adds 1 to r. So the inner loop contributes j to the total. That means the whole function is really adding up a pile of j-values:

r = Σ_i=1ⁿ⁻¹ Σ_j=i+1ⁿ j

Do not panic at the double sum — the point is only its shape. There are three loops stacked inside each other, and all three ranges grow with n: the outer runs about n times, the middle about n times, and the inner up to n times. A quantity that is "about n, times about n, times about n" is cubic — proportional to n³. Every extra factor of n from a nested loop that grows with the input multiplies the work again, exactly the "loops inside each other multiply" rule from §7.7, here applied three times.

So the returned value r is a cubic polynomial in n, and the worst-case running time is Θ(n³), i.e. O(n³). (There is no early return or data-dependent branch, so best and worst case are the same — the loops always run to completion.) Confirm both claims with a counter, and watch the tell-tale ×8 when you double n:

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

The counter matches the value the function returns, and each doubling of n multiplies r by roughly 8. A ×8 response to a ×2 input is the fingerprint of cubic growth: 2³ = 8, just as a ×4 response meant an exponent of 2 in §7.6.

Counting by j instead of by the loops makes it exact: each value j (from 2 to n) is reached by j−1 choices of i, so r = Σj=2n j(j−1) = (n3 − n)/3. Check: n = 5 gives (125−5)/3 = 40, exactly what the function returns.

Answer: mystery(n) returns r = (n3 − n)/3, and its worst-case running time is Θ(n³). Doubling n multiplies the value by about 8, confirming the cube.

Again begin at the innermost loop. It runs k = j .. i+j. The number of integers from j to i+j inclusive is

(i + j) − j + 1 = i + 1.

Notice what happened: the j cancelled clean out. However far up the range starts, its length is always i + 1 — it does not depend on j at all. That is the whole trick of this problem. So the inner loop contributes i + 1 every time, and the two outer loops just repeat that:

r = Σ_i=1ⁿ Σ_j=1ⁱ (i + 1) = Σ_i=1ⁿ i·(i + 1)

The middle line simplifies because the summand (i + 1) does not mention j, so adding it up i times (as j runs from 1 to i) is just multiplying it by i — giving i(i+1). Now i(i+1) = i² + i, and summing a term that grows like i² across n values of i lands us at something proportional to n³. (The tidy closed form is n(n+1)(n+2)/3, plainly a cubic — but you do not need it to see the shape.)

Confirm the value and the class with a counter, comparing against that closed form:

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}")

The counter sits exactly on n(n+1)(n+2)/3. The doubling ratios here (70 → 440 → 3080, about 6.3× then 7.0×) are still climbing towards 8 rather than sitting on it, because at these small sizes the lower-order +n² and +n parts of the cubic have not yet faded — push n higher and the ratio settles on 8, exactly the "small inputs are noisy, the trend is cubic" story of §7.3.

Answer: The inner loop always runs (i+j)−j+1 = i+1 times, so pesky(n) returns Σ_i=1ⁿ i(i+1) = n(n+1)(n+2)/3, a cubic polynomial, and its running time is Θ(n³) = O(n³).

(a) The nested-sum form. Each loop becomes one summation sign, and the printed line — the thing we are counting — is the "1" being summed at the very centre. Reading the ranges straight off the loops:

T(n) = Σ_i=1^n/2 Σ_j=iⁿ⁻ⁱ Σ_k=1^j 1

The innermost sum, Σk=1j 1, is just "add 1 to yourself j times", which equals j. Substituting that collapses the triple sum to a double one:

T(n) = Σ_i=1^n/2 Σ_j=iⁿ⁻ⁱ j

The inner sum now adds up the whole numbers from j = i up to j = n − i. That is a run of consecutive integers, and a run of consecutive integers up to about n adds up to something on the order of n² (the triangular-number idea from §7.6: 1 + 2 + … + m ≈ m²/2). So the inner sum alone is already quadratic in n for the early values of i.

(b) Simplify. We then repeat that quadratic amount of work for each i from 1 up to n/2 — that is, about n more times. "About n²" of work, done "about n" times, is cubic. So T(n) = Θ(n³) = O(n³). The n/2 and the shrinking i .. n−i window only change constant factors — half a cube is still a cube, exactly as half a square was still a square in §7.6 — they do not touch the class.

Confirm the cube with a counter that tallies the prints instead of doing them:

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

Each doubling multiplies the print count by exactly 8 — a clean ×8 on a ×2, the signature of Θ(n³).

Show the work explicitly. The inner sum of j from i to n−i is [(n−i)(n−i+1) − (i−1)i]/2; writing n = 2m:

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

Answer: (a) T(n) = Σ_i=1^n/2 Σ_j=iⁿ⁻ⁱ Σ_k=1^j 1, which simplifies to Σ_i=1^n/2 Σ_j=iⁿ⁻ⁱ j once the inner sum of 1's is replaced by j. (b) Carrying the sums through exactly (write n = 2m; the inner sum of j from i to n−i summed over i = 1..m) collapses to the clean closed form T(n) = m3 = (n/2)3 = n3/8. Check: n = 4 gives 8 and n = 10 gives 125, both matching a direct count. So T(n) = n3/8 = Θ(n3) — confirmed by the ×8-per-doubling counter.

(a) Worst case. Look inside the loop and just count the arithmetic. The line xpower = x * xpower is one multiplication. The line p = p + a[i] * xpower is one multiplication (a[i] * xpower) and one addition (p + …). So every pass of the loop costs two multiplications and one addition, and the loop runs n times (for i = 1 .. n). Total: 2n multiplications and n additions.

(b) Average case. Here is the quiet insight: there is no if, no break, nothing in this loop that depends on the values of the coefficients or of x. The loop always runs the same n times and always does the same arithmetic each pass. When behaviour never branches on the data, the average case cannot differ from the worst case — so the average is also 2n multiplications. (Contrast the linear search of §7.5, whose count did depend on where the target sat.)

(c) Can we do better? Yes — Horner's rule. The waste in the naive method is that first multiplication, the one that keeps rebuilding xpower. Horner's rule rewrites the polynomial by factoring x out repeatedly — a₀ + x(a₁ + x(a₂ + … )) — so each step folds in one coefficient with a single multiply-and-add:

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

Now the loop body is a single p * x + a[i]: one multiplication and one addition per pass, over n passes. That is n multiplications and n additions — the additions are unchanged, but the multiplications have been halved, from 2n to n. The reason it needs only n multiplications is that it never builds the powers of x separately; each existing running total is multiplied by x exactly once as the next coefficient is folded in.

Check that both agree on the answer while the counts differ:

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))

Both return 32, but the naive method spent 6 multiplications (2n = 2×3) where Horner's rule spent only 3 (n = 3). Same additions, half the multiplications — and both are still O(n), the best class possible since you must at least touch every coefficient once.

Answer: (a) 2n multiplications and n additions in the worst case. (b) 2n multiplications on average too, because the loop has no data-dependent branch, so average equals worst. (c) Yes — Horner's rule, p = p*x + a[i] evaluated from the top coefficient down, uses only n multiplications and n additions, halving the multiplications.