Week 06 — Doubling experiments, plots, and noisy evidence

The question for this week

When the input becomes twice as large, how much more work does the algorithm do?

Week 5 established a repeatable task and a clearly placed stopwatch. Now change input size systematically. The purpose is to develop a useful hypothesis about growth, then check that hypothesis against the code. A measured ratio is evidence; even a beautiful table is not a proof that the same pattern holds for every future input.

The core outcomes are to build a doubling table, calculate ratios, label an ordinary plot, recognize misleading measurements, and write a defensible prediction. Logarithmic growth and log–log slopes are second-pass material: revisit them in Weeks 7–8 if the core ideas need more time. Review B supplies the longer scheduled review session; use this chapter to identify what needs repair.

Türkçe: İki kat veri, iki kat süre demek zorunda değildir. Amacımız değişimin şeklini görmek, sonra kodun yaptığı işlemlerle açıklamaktır. Ölçümden gelen tahmin ile bütün girdiler için geçerli matematiksel kanıtı ayırmalıyız.

Prerequisite warm-up, with answers

1. A task takes 0.12 s, then 0.48 s at double the input. What is the ratio? Answer: 0.48/0.12 = 4. Divide the later observation by the earlier one.
2. What does n² mean when n = 6? Answer: 6×6 = 36. At n = 12 it becomes 144, which is four times 36.
3. What is log₂8? Answer: 3, because 2³ = 8. A logarithm asks for an exponent.
4. What is wrong with timing sorted(make_data(n)) and reporting sorting alone? Answer: input construction is also inside the measured call. Prepare the data before starting the sorting timer.

Keep these units distinct: n is an input size, a count is a number of chosen operations, and a duration is seconds. A ratio of two durations has no time unit because seconds cancel.

1. The ratio is a question about change

Write T(n) for the cost at size n. The doubling ratio is T(2n)/T(n). At the first size there is no earlier observation, so put a dash rather than inventing a meaningful first ratio.

The following table describes ideal cost models, not guaranteed timing behavior:

Here c is a positive fixed multiplier. In a timing model it incorporates implementation and machine effects that are assumed stable over the comparison. That assumption sometimes fails. Ratios can reduce the influence of a fixed multiplier; they do not magically remove every hardware effect.

Worked example 1 — derive the quadratic ratio

Suppose a counter visits every ordered pair from n items. There are n choices for the first item and n for the second, hence n×n = n² visits.

This is an exact deterministic count. Algebra explains every doubling: (2n)²/n² = 4n²/n² = 4 for n > 0. A finite table checks our calculations; the formula establishes the pattern for all positive n.

def pair_visits(n):
    count = 0
    for first in range(n):
        for second in range(n):
            count += 1
    return count

previous = None
for n in [4, 8, 16, 32]:
    count = pair_visits(n)
    ratio = '-' if previous is None else f'{count / previous:.2f}'
    print(n, count, ratio)
    assert count == n * n
    previous = count

Türkçe: Birinci seçimin n, ikinci seçimin n olasılığı vardır. Çarpım n²’dir. n yerine 2n yazınca yalnızca bir faktör değil, iki faktör de iki katına çıkar: 2×2 = 4.

2. Design a doubling experiment that can finish

Choose one task and input family. A missing-target search forces a full scan; searching for the first element measures a different case. A duplicate finder can stop early when a duplicate appears, so “random data” does not automatically produce its worst case. For sorting, preserve whether the input is shuffled, already sorted, or reverse ordered.

Use a pilot size before committing to several doublings. Doubling a quadratic task four times multiplies its final cost by 4⁴ = 256. Starting at 0.1 s could lead to an approximately 25.6 s final trial under a stable quadratic model. Choosing smaller sizes is a way to keep the experiment bounded, not a way to hide poor scaling.

The following block demonstrates the mechanics on small deterministic inputs. It records actual times, so its output depends on the environment. It makes no automatic complexity verdict from those short observations.

import time

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

previous = None
for n in [1000, 2000, 4000, 8000]:
    data = list(range(n))
    assert contains(data, -1) is False
    samples = []
    contains(data, -1)  # explicit untimed warm-up
    for repeat in range(5):
        start = time.perf_counter()
        contains(data, -1)
        samples.append(time.perf_counter() - start)
    best = min(samples)
    ratio = '-' if previous is None or previous <= 0 else f'{best / previous:.2f}'
    print(n, 'observed seconds:', samples, 'minimum ratio:', ratio)
    previous = best

The list is built before timing. Repeats use the same prepared data, and printing follows the timer. For a task that mutates its input, give every timed trial a fresh equivalent input outside its timed region; otherwise later trials may solve an easier problem.

3. Optional second pass — logarithmic and n log n growth

For a halving loop, log₂n counts approximately how many halvings are needed to reduce n to one. The sequence n = 8, 16, 32, 64 has logarithms 3, 4, 5, 6. Doubling adds one step. Its ratios are 4/3, 5/4, 6/5: they move toward 1, even though the work is not constant.

For T(n) = n log₂n, divide the doubled model by the original:

T(2n)/T(n)
= [2n × log₂(2n)] / [n × log₂n]
= [2n × (1 + log₂n)] / [n × log₂n]
= 2 + 2/log₂n.

At n = 16, the ratio is 2 + 2/4 = 2.5. At n = 256, it is 2 + 2/8 = 2.25. At n = 65536, it is 2 + 2/16 = 2.125. There is no single universal “sorting ratio of 2.2.” A ratio near 2 does not separate linear from linearithmic growth by itself, and adaptive sorting can exploit particular input orderings.

Türkçe: Logaritmik büyümede iki kat veri bir ek adım getirir. n log n için ise hem n faktörü iki katına çıkar hem logaritmaya 1 eklenir. Bu nedenle oran 2’nin biraz üstündedir ve n arttıkça 2’ye yaklaşır.

4. Read plots without losing the question

A linear-axis plot puts input size n horizontally and measured time in seconds vertically. State the operation counted if plotting counts instead. Include a title and a legend when comparing methods. A line connecting sampled points is an aid to reading, not evidence that all intermediate or future points were measured.

Optional second pass — logarithmic axes and slopes

You may move directly from the ordinary-plot paragraph to Section 5 on noise. This extension can wait until Weeks 7–8; it is not required for core readiness.

A log–log plot transforms both axes. Equal spacing now represents equal multiplicative changes. Sizes 10, 100, 1000 are equally spaced in base-10 logarithms because their logs are 1, 2, 3. Zero and negative values cannot appear on ordinary logarithmic axes; never replace a zero timing with an unexplained tiny number just to make the plot work.

For a power model T = cnᵏ, logarithms give:

log T = log c + k log n.

Define x = log n and y = log T. Then y = log c + kx, a straight line with slope k. A constant model has slope 0; linear has slope 1; quadratic has slope 2. The constant multiplier shifts the line vertically. A model such as n log n is not exactly a fixed power, so its log–log curve need not be exactly straight.

The original lesson supplies Matplotlib commands for drawing these figures. You can understand and check the transformed coordinates using a table or paper before using the plotting interface.

Worked example 2 — calculate a slope

Use deterministic counts n², not invented timings. Between n = 4 and n = 16, the input ratio is 16/4 = 4 and the count ratio is 256/16 = 16. The log–log slope is log₂16/log₂4 = 4/2 = 2.

A line fit uses all points. Let x and y be their logged coordinates, and x̄ and ȳ their averages. The least-squares slope is the sum of (x − x̄)(y − ȳ) divided by the sum of (x − x̄)². This is the calculation behind the lesson's polyfit call. Here is a version using only the standard library:

import math

sizes = [4, 8, 16, 32]
counts = [n * n for n in sizes]
xs = [math.log(n) for n in sizes]
ys = [math.log(count) for count in counts]
x_mean = sum(xs) / len(xs)
y_mean = sum(ys) / len(ys)
numerator = sum((x - x_mean) * (y - y_mean) for x, y in zip(xs, ys))
denominator = sum((x - x_mean) ** 2 for x in xs)
slope = numerator / denominator
print(f'Fitted slope of exact quadratic counts: {slope:.2f}')
assert abs(slope - 2) < 1e-12

zip pairs corresponding coordinates. A fit can summarize multiple observations, but one outlier can still affect it. Inspect the points, residuals and sampled range instead of treating the fitted slope as an unquestionable tie-breaker.

5. Three reasons a ratio can mislead

Small-signal noise: a short task can have timing variation comparable to the work itself. Repetition, batching, and cautiously increasing n may help. Merely printing more decimal places cannot.

Fixed overhead and lower-order work: if T(n) = 1000 + n in chosen units, T(20)/T(10) = 1020/1010 ≈ 1.01. The growth-dependent part is linear, but the setup cost dominates these sizes. A low ratio does not prove constant work.

Changing conditions: cache capacity, memory allocation, CPU frequency, input distribution and competing tasks can change per-item cost. A ratio above 2 for a known linear scan does not instantly make its operation count quadratic. Conversely, do not dismiss every disagreement as noise: it might expose a hidden operation or incorrect model.

An honest interpretation says what was measured, gives actual sizes and ratios, names a hypothesis, explains it using the code, identifies limitations, and states any prediction conditionally. Do not write a made-up fitted slope or crossover merely because the lesson suggests what might occur.

6. Graduated practice with complete solutions

Practice 1 — classify an exact table

For n = 10, 20, 40, the chosen operation counts are A: 30, 60, 120 and B: 100, 400, 1600. Find both ratio columns and formulas consistent with the table.

Solution 1

A has ratios 60/30 = 2 and 120/60 = 2, consistent with 3n. B has ratios 400/100 = 4 and 1600/400 = 4, consistent with n². A formula derived from the code would justify extending these patterns. Three matching rows alone do not uniquely determine a function.

Practice 2 — make and qualify a prediction

Illustratively, a stable quadratic model takes 0.08 seconds at n = 200. Predict n = 600. A later observation is 0.78 seconds. Find the prediction error relative to the prediction.

Solution 2

Input multiplier = 600/200 = 3. Cost multiplier = 3² = 9. Predicted duration = 0.08×9 = 0.72 s. Difference = 0.78−0.72 = 0.06 s. Relative error = 0.06/0.72×100 ≈ 8.33%. Report the model and difference; investigate input preparation, noise, memory behavior and lower-order terms. These numbers are an arithmetic exercise, not a benchmark performed here.

Practice 3 — expose the hidden measurement

A wrapper builds a list, shuffles it, sorts it, and prints it inside a timer. Its ratios approach 2.2. Is sorting proved to be n log n? Give a corrected experiment and a defensible conclusion.

Solution 3

No. The measured task combines generation, shuffle, sort and output. Prepare deterministic shuffled inputs outside timing, preserve equivalent input conditions between trials, time sorting alone, and print afterward. Record individual samples and the summary policy. Compare the sorting implementation's known operation bound with the observations. A defensible statement is “the measured range is consistent with the proposed sorting model under these conditions,” not “the ratio proves the bound.”

Misconceptions to repair

• “A ratio of four proves quadratic time.” It supports that model on the sampled range; count the code to justify a general bound.
• “A fitted line removes noise.” A fit can still be distorted by outliers or changing conditions; inspect the individual observations.
• “A slower run means the algorithm changed.” The operation count may be unchanged while the environment or input case differs. State both.

Glossary, readiness, and transition

Core readiness means deriving ratios 2 and 4, labelling an ordinary plot with input size and time units, calculating a prediction, and challenging a suspicious table. If ratios are unclear, write units on numerator and denominator. If your conclusion is stronger than the evidence, rewrite Practice 3. Use Review B for those repairs.

Optional second-pass readiness means explaining how doubling affects logarithmic work and reading a log–log slope. If logs are unclear, rebuild the powers-of-two warm-up when you return to these sections in Weeks 7–8; this does not block your Week 7 core work.

Bridge to Week 7: the stopwatch suggests a pattern. A line-by-line operation count explains why it arises, even when a shared computer gives noisy times.

What happens when the input doubles?

Let n be the number of input items. Work proportional to n doubles when n doubles. Work proportional to n squared becomes four times as large. Timings also include fixed extra work and small variations, so one timing ratio cannot prove a growth pattern.

Draw or trace. Draw squares of side n and 2n. The larger square contains four copies of the smaller. Compare this with two line segments of lengths n and 2n.

Predict before checking. For an illustrative model T(n) = 100 + n, is T(2n)/T(n) exactly 2? What happens as n increases?

Worked reasoning

At n = 10, the ratio is 120/110, about 1.09. At n = 1000, it is 2100/1100, about 1.91. The fixed 100 matters more when n is small. These numbers come from the formula; they are not measured times. A ratio near one may simply mean the fixed work is large, not that the algorithm always takes constant time.

for n in (10, 1000):
    ratio = (100 + 2 * n) / (100 + n)
    assert 1 < ratio < 2
    print(n, round(ratio, 3))

Change one thing. Replace the model with 100 + n*n. Predict its large-input ratio and explain why you still need counts and repeated timings for real code.

Türkçe: İkiye katlama oranı varsayımlara bağlı bir ipucudur. Küçük girdide sabit ek yük büyümeyi gizleyebilir; tek oran kanıt değildir.

Additional analysis laboratory

The doubling experiment is a pattern detector. It should train caution, not overconfidence. Ratios near 2 or 4 suggest a model over the tested range, but the explanation comes from the code and count.

Extra exam-style prompt: Timings are 0.003, 0.006, 0.013, and 0.026 seconds for n = 500, 1000, 2000, 4000. What should the report say?

Solution: Ratios are about 2, 2.17, and 2. The measurements support roughly linear scaling over these sizes. The report should also state repeat policy, timer boundary, variability, and the code reason for one pass. It should not claim a proof from timings alone.

Turkce: Oranlar ipucu verir. Kanit yerine gecmez. Bir tablo yazdiktan sonra mutlaka "hangi is tekrar ediyor?" sorusuna don.