Week 07 — Exact operation counts and dominant growth

The question for this week

Can we explain an algorithm's work without depending on the speed of the computer that runs it?

Week 6 supplied observational evidence. This week develops an explicit model. We choose what to count, read loop bounds carefully, derive a formula, and then simplify its growth. The exact formula and the growth description answer different questions. Keep both until you understand why terms can be ignored for one purpose but not the other.

You should finish able to count a linear scan, distinguish sequential from nested work, derive a triangular sum, handle a fixed inner bound, compare constant factors, recognize halving, and use the RAM model honestly. The later chapter problems extend the same tools to dependent triple loops and polynomial evaluation.

Türkçe: Süre ölçümü bilgisayardan etkilenir. İşlem sayısı için önce neyi “bir işlem” saydığımızı belirleriz. Tam formül ile büyüme sınıfı aynı şey değildir: biri belirli n için sayıyı, diğeri n büyürken davranışı anlatır.

Prerequisite warm-up, with answers

1. How often does range(5) run? Answer: five times, for 0 through 4.
2. How many integers are in the inclusive interval 3 through 7? Answer: 7−3+1 = 5. Subtract endpoints and add one.
3. If one loop performs 4 operations and a later loop performs 6, how many altogether? Answer: 4+6 = 10, not 24.
4. If each of 4 outer iterations performs 6 inner operations, how many altogether? Answer: 4×6 = 24.
5. What happens to 3n² when n doubles? Answer: 3(2n)² = 12n², four times the original 3n².

If the second answer was not immediate, trace inclusive and exclusive ranges on paper before tackling dependent loops. Most errors below come from endpoints rather than advanced mathematics.

1. Declare the counted operation

Let n denote input size and T(n) denote a chosen operation count. For sum_to(n), the original lesson first counts assignments:

def sum_to(n):
    total = 0
    for number in range(1, n + 1):
        total = total + number
    return total

assert sum_to(5) == 15
print(sum_to(5))

There is one initialization of total, n assignments to the loop variable number, and n assignments updating total. Under that declared convention, T(n) = 1+2n. For n = 5, this is 11 assignments. If we count only additions instead, the count is n = 5. Neither number is “the exact cost” without its counting convention.

The unit-cost Random Access Machine, or RAM model, treats ordinary operations on machine-sized values as constant-cost steps. Arithmetic, comparisons, assignments and array access receive fixed costs. This helps compare algorithmic structure without choosing a particular laptop. It does not claim a real division and addition take identical nanoseconds.

Be careful with the word “ordinary.” Comparing arbitrarily long strings can inspect many characters. Multiplying huge Python integers can depend on their bit lengths. Calling sorted is not one constant-time sorting operation merely because it occupies one source line. The model must describe the work that matters.

Different representative operations often yield the same growth class when each iteration performs a bounded amount of work. Counting only the final return would miss an expensive loop completely. Choose a count that actually represents the expensive region.

2. Sequential, rectangular, fixed, and triangular loops

Worked example 1 — four loop shapes

Count body updates only, excluding setup and loop-control assignments. Use n = 4 first.

The fixed-inner case is the important trap. Ten is independent of n. Multiplying n by ten changes the multiplier, not the power of n. In the rectangular case, both dimensions grow with n, so their product is quadratic.

n = 4
sequential = 0
for i in range(n):
    sequential += 1
for j in range(n):
    sequential += 1

rectangle = 0
fixed_inner = 0
triangle = 0
for i in range(n):
    for j in range(n):
        rectangle += 1
    for j in range(10):
        fixed_inner += 1
    for j in range(i):
        triangle += 1

print(sequential, rectangle, fixed_inner, triangle)
assert (sequential, rectangle, fixed_inner, triangle) == (8, 16, 40, 6)

This program verifies four specific counts; the formulas explain all n. If we instead count all assignments in the rectangular loop, the initializer contributes 1, the outer loop variable n, the inner loop variable n², and the body counter n². That gives 1+n+2n². It is not the same exact formula as n², but both have quadratic dominant growth. Differences between conventions need not be only one or two operations.

Derive the triangular formula slowly

For the triangular loop, i takes 0, 1, …, n−1, and the inner loop runs i times. Write the sum forward and backward:

S = 0 + 1 + 2 + ... + (n−1)
S = (n−1) + (n−2) + ... + 0
2S = (n−1) + (n−1) + ... + (n−1), with n terms
2S = n(n−1)
S = n(n−1)/2 = n²/2 − n/2.

The factor one-half does not remove the square. At n = 10 the count is 10×9/2 = 45. At n = 20 it is 20×19/2 = 190. The ratio 190/45 ≈ 4.222 is not exactly 4 because the linear term still matters. Ratios approach 4 as n grows.

Türkçe: İç döngü her seferinde n kez çalışmıyorsa doğrudan n×n yazmayın. Önce her dış tur için iç tur sayısını bulun, sonra toplayın. 0+1+…+(n−1), kare büyümenin yarısıdır; doğrusal büyüme değildir.

3. A dominant term describes large-input behavior

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

At n = 10, the constant contributes more than the squared term. At n = 1000, the squared term contributes about 96.1% of the total. Dividing the formula by n² makes the reason visible: T(n)/n² = 5 + 200/n + 3000/n². The last two terms shrink toward zero; the ratio approaches 5.

For growth classification, keep n². For predicting actual operation totals at n = 10, keep all terms. Small inputs can matter in engineering, especially if a small task runs millions of times. “Ignore lower terms” is a rule for asymptotic simplification, not permission to erase them from every calculation.

Worked example 2 — solve a crossover

Method A costs 100n operations; method B costs n². For positive n, equality requires:

100n = n²
100 = n, after dividing both sides by n.

For n > 0, B/A = n²/(100n) = n/100. At n = 1000, B uses ten times the modeled work. The operation-model crossover is exactly 100. A measured time crossover can differ because the two implementations' operations have different real costs.

Türkçe: Sabit çarpan küçük girdilerde sonucu değiştirebilir. Ancak 100n ile n² karşılaştırmasında n/100 oranı sınırsız büyür. Önce eşitlik noktasını hesaplayın, sonra bu noktanın hangi tarafında olduğunuzu belirleyin.

4. Adding a constant versus shrinking by a factor

A loop that changes i from 0 toward n using i += 1 runs n times. A loop beginning at n and applying i //= 2 while i > 1 shrinks much faster.

For n = 20, the halving states are 20 → 10 → 5 → 2 → 1, giving four iterations. For n = 16 they are 16 → 8 → 4 → 2 → 1, also four. For integer n ≥ 1, this floor-halving loop has floor(log₂n) iterations. For powers of two, n = 2ᵏ, the count is exactly k.

The phrase “multiply means logarithmic” needs context. Multiplying the progress variable by a fixed factor can make the iteration count logarithmic. An algorithm that creates twice as many recursive subproblems each level can instead produce exponential total work. Identify what quantity changes, its stopping condition, and the work per iteration.

5. Optional deepening — after the core check: dependent loops

First check that you can explain the four simple loop shapes in Section 2. The following chapter problems preserve the original lesson’s deeper material; their cubic formulas are not prerequisites for Week 8. Return after the core check, using the same method: start at the innermost loop, find its length, then add over the surrounding choices.

Mystery: group by the middle index

In the mystery function, i runs from 1 to n−1; j runs from i+1 to n; k runs from 1 to j. For a fixed j, there are j−1 possible i values and j inner iterations. Thus that j contributes j(j−1).

Adding over j = 2 through n gives the sum of j² minus the sum of j. Using the standard sums:

r = n(n+1)(2n+1)/6 − n(n+1)/2
  = n(n+1)[(2n+1)−3]/6
  = n(n+1)(n−1)/3
  = (n³−n)/3.

At n = 5, r = (125−5)/3 = 40. The dominant term is cubic. This grouping argument is stronger than merely noticing three visible loops.

Pesky: cancel the lower endpoint

Here i runs 1 through n; j runs 1 through i; k runs j through i+j inclusive. The inner length is (i+j)−j+1 = i+1. Its starting position changes with j, but its length does not.

There are i choices of j, giving i(i+1) updates for each i. Summing i²+i yields n(n+1)(n+2)/3. At n = 5, the result is 5×6×7/3 = 70. The lower-degree terms explain why small-input doubling ratios are below 8; this is not timing noise, because these are exact counts.

Foobar: a shrinking interval still has cubic total work

Take even n = 2m. The outer i runs 1 through m, j runs i through 2m−i, and the inner loop runs j times. Summing j over that interval gives its average m multiplied by its length 2m−2i+1.

Therefore the whole count is m times the sum (2m−1)+(2m−3)+…+1. The first m odd numbers sum to m², so total updates = m×m² = m³ = n³/8. For n = 4, there are 8 updates; for n = 10, 125. Doubling even n multiplies this exact formula by 8.

6. Optional deepening — polynomial evaluation

The source evaluates a₀+a₁x+…+aₙxⁿ using a running power of x. Each of n iterations updates the power with one multiplication, then multiplies by a coefficient and adds to the result. Total: 2n multiplications and n additions. With no data-dependent early exit, those counts do not change between best, average and worst coefficient values under this model.

Horner's method rewrites the expression as a₀+x(a₁+x(a₂+…)). Work from the highest coefficient downward. For 2−3x+x²+4x³ at x = 2:

Direct substitution agrees: 2−6+4+32 = 32. Horner uses n multiplications and n additions: half the multiplications of this particular running-power method. Both are linear in the number of coefficients. The “naive” method here does not recompute every power from scratch; that would be a different implementation with different counts.

7. Graduated practice with complete solutions

Practice 1 — exact count versus growth

Count body updates for two sequential loops of lengths n and 3n, followed by one fixed loop of length 7. Evaluate n = 5 and simplify the growth.

Solution 1

Sequential regions add: n+3n+7 = 4n+7 updates. At n = 5, that is 20+7 = 27. The dominant term is linear. The exact value 27 depends on including the final seven updates; the growth class does not.

Practice 2 — implement and verify the triangle

Count count += 1 in an outer range(n) and inner range(i). Verify n = 0, 1, 4, 8, and explain the ratio from 4 to 8.

Solution 2

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

for n, expected in [(0, 0), (1, 0), (4, 6), (8, 28)]:
    actual = triangular_count(n)
    assert actual == n * (n - 1) // 2 == expected
    print(n, actual)
print('Ratio from 4 to 8:', 28 / 6)

The ratio is 28/6 ≈ 4.667. The formula has a negative linear term, so the small-size ratio is not exactly four. Do not calculate ratios whose denominator is zero, such as the count at n = 1.

Practice 3 — optional challenge: verify Horner's arithmetic and savings

Evaluate coefficients [2, -3, 1, 4] at x = 2 using Horner, count multiplications, and compare with the lesson's running-power method. State what n means.

Solution 3

coefficients = [2, -3, 1, 4]
x = 2
degree = len(coefficients) - 1
value = coefficients[-1]
multiplications = additions = 0
for i in range(degree - 1, -1, -1):
    value = value * x + coefficients[i]
    multiplications += 1
    additions += 1
print(value, multiplications, additions)
assert (value, multiplications, additions) == (32, 3, 3)

Here n is polynomial degree 3, and there are n+1 = 4 coefficients. The running-power method uses 6 multiplications and 3 additions. Horner saves 3 multiplications. The result and the asymptotic class are unchanged; the operation count improves.

Misconceptions, glossary, and readiness

You are ready when you can derive 2n, n², 10n and n(n−1)/2 without guessing from indentation alone. If not, trace n = 4 and label the counted update. The dependent triple-loop proofs and Horner challenge can wait. When revisiting them, redo the inclusive-length warm-up and the pesky cancellation. If exact counts and growth labels are mixed together, keep two separate columns in your answers.

Bridge to Week 8: now that you can justify a cost formula, you are ready to express an upper bound precisely and distinguish it from a tight description of growth.

Draw the work before writing its formula

Add counts for tasks done one after another. Multiply when every item is paired with every item. If an inner loop runs a different number of times on each round, add those actual counts. Seeing two loops is not enough to decide how the work grows.

Draw or trace. Draw a 4 by 4 grid for every ordered pair. Then mark only pairs with column less than row: row lengths are 0, 1, 2, 3. These dots represent actual visits.

Predict before checking. How many visits occur in the square and triangle? Why does the triangle represent each unordered pair of distinct indices once?

Worked reasoning

The square has 16 visits; the triangle has 6. For n items, the triangle gives 0 + 1 + ... + (n − 1) = n(n − 1)/2. Each pair of different positions appears once, without counting the reversed pair again. Two such triangles count both orders. Two separate full scans take n + n visits, not n squared. To use visits as a time estimate, assume each visit does a fixed amount of work.

for n in (0, 1, 4, 10):
    pairs = [(i, j) for i in range(n) for j in range(i)]
    assert len(pairs) == n * (n - 1) // 2
print("Four items give", len([(i, j) for i in range(4) for j in range(i)]), "pairs")

Change one thing. Make the inner loop always run three times. There are still two loops, but now there are 3n body visits. State what changed geometrically.

Türkçe: Döngü sayısını değil ziyaret edilen işi say. Ardışık işler toplanır; değişen iç döngü uzunlukları bir toplam oluşturur.

Additional analysis laboratory

Exact counting is where students learn to slow down. The safest method is to write the loop shape before simplifying.

Extra exam-style prompt: A program first scans n readings to compute a maximum, then compares every pair of readings. Give the exact pair-comparison count and the total growth.

Solution: The first scan contributes n visits or n - 1 comparisons depending on the chosen count. The pair phase has n(n - 1)/2 unordered comparisons if each distinct pair is checked once. The total is linear plus quadratic, so the dominant growth is quadratic.

Turkce: Ard arda gelen isleri topluyoruz. Ic ice ve her kombinasyonu deneyen islerde carpma veya toplam cikiyor. Son adimda en buyuk terim buyume davranisini belirler.