Week 05 — Functions and trustworthy timing

The question for this week

How can we run the same piece of work with different inputs, then measure it without measuring something else by accident?

Earlier weeks used variables and loops to describe algorithms. This week packages those steps into functions and adds a stopwatch. These are separate skills: a function can be correct while its benchmark is misleading, and a carefully measured function can still calculate the wrong answer. Check correctness first, timing second.

By the end, you should be able to explain a parameter, an argument, and a return value; define a reusable function; place a timer around a clearly stated task; repeat measurements; distinguish clock resolution from practical measurement accuracy; and choose between perf_counter and timeit. You should also know what a timing table cannot establish.

Türkçe: Önce “hangi işi yapıyorum?” sorusunu kesinleştiririz. Fonksiyon o işi tekrar kullanmamızı sağlar; zaman ölçümü ise işin belirli bir ortamda ne kadar sürdüğünü gösterir. Doğru sonuç, doğru ölçüm ve büyüme analizi birbirinin yerine geçmez.

Prerequisite warm-up, with answers

1. What values does range(1, 5) produce? Answer: 1, 2, 3, 4. Its stop value is excluded.
2. Starting with total = 0, what follows adding 1, then 2, then 3? Answer: the successive totals are 1, 3, 6.
3. What is 15% as a decimal? Answer: 15/100 = 0.15. Conversely, a fraction becomes a percentage by multiplying by 100.
4. A clock reads 12.400 seconds before work and 12.425 afterward. What elapsed? Answer: 12.425 − 12.400 = 0.025 seconds = 25 milliseconds.

If the last conversion was difficult, keep these equalities visible: 1 second = 1000 milliseconds; 1 millisecond = 1000 microseconds. A smaller unit produces a larger numerical reading for the same interval.

1. A function has an input, a job, and a result

Consider this complete program:

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

answer = sum_to(4)
print(answer)
assert answer == 10
assert sum_to(0) == 0

def creates the function. The indented lines are its body. The name n is a parameter: a local name ready to receive a value. In sum_to(4), 4 is the argument supplied by this particular call. The call begins the body, and return total hands its result to the caller. Assignment then stores that returned result in answer.

Defining the function does not execute its loop. Calling it does. Calling it again starts a fresh total = 0; it does not continue the previous call's total. Here the input contract is a non-negative integer n. Negative or fractional inputs need a separate specification rather than an accidental interpretation of range.

Worked example 1 — trace before running

For n = 4, range(1, n + 1) becomes range(1, 5).

The arithmetic is 1 + 2 + 3 + 4 = 10. The table also shows why initialization belongs outside the loop. Moving total = 0 inside would repeatedly erase earlier additions.

print(total) and return total do different jobs. Printing displays text. Returning supplies a value that another calculation can use. A function that only prints and then reaches its end returns None. Therefore, when answer unexpectedly becomes None, inspect the function's return paths before blaming the arithmetic.

Türkçe: print ekrana yazar; return çağırana değer verir. Parametre tanımdaki isimdir, argüman çağrıda verdiğimiz değerdir. Her çağrıda yerel toplam yeniden sıfırdan başlar.

2. Put boundaries around the measured task

time.perf_counter() provides a clock suitable for elapsed intervals. Its absolute reading is not a date or an execution time. Subtract two readings to obtain an interval. It is monotonic: it does not move backward when the wall clock is adjusted. This is why it is preferable to time.time() for these measurements.

import time

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

n = 1000
start = time.perf_counter()
answer = sum_to(n)
elapsed = time.perf_counter() - start
assert answer == 500500
print("Answer:", answer)
print("Observed seconds:", elapsed)

This small run demonstrates timer placement. Its short duration is not sufficient evidence for a growth classification. Your observed number will vary. There is no fixed expected timing to copy.

For a search benchmark, decide whether the task is “search an existing list” or “construct a list and search it.” Both questions can be legitimate. They need different timer boundaries. If you claim to measure search alone, build the list before starting the clock. Keep printing outside the timed interval because formatting and console output are additional work.

Record the function, input size, input contents or generation rule, chosen case, repetition count, and summary statistic. “The algorithm took 0.02 seconds” omits almost everything another person needs to interpret the result.

3. Repetition, warm-up, and noise

A computer shares its resources among many tasks. Scheduling, CPU frequency, cache state, memory allocation and garbage collection can change observed time. Repeat the same stated experiment instead of trusting one lucky or unlucky run.

The lesson's minimum-of-repeats harness is useful when asking about relatively uninterrupted execution. The minimum is the smallest observation. The mean is total time divided by the number of observations. The median is the middle value after sorting, or the mean of the middle two when there is an even count. Report which one you use.

Worked example 2 — summarize illustrative observations

The following values are illustrative arithmetic data, not measurements made for this guide: 12, 8, 9, 8, 13 milliseconds.

If we deliberately exclude the first observation, the mean becomes (8 + 9 + 8 + 13)/4 = 38/4 = 9.5 ms. The minimum remains 8 ms. This demonstrates the arithmetic of a warm-up policy; it does not prove the first observation was a warm-up effect.

The first call may pay one-time costs and be slower. It is not guaranteed to be the slowest. An explicit untimed warm-up makes the policy understandable. Taking a minimum is not a universal substitute for controlling the experiment, and does not reveal a unique hardware-independent “true time.” For workloads where cold-start behavior matters, discarding it would answer the wrong question.

Türkçe: En küçük süre “kesin gerçek süre” değildir; gözlenen koşullardan birini temsil eder. İlk çalıştırmayı çıkarıyorsanız neden çıkardığınızı yazın. Sıcak başlangıç ile ilk kullanım performansı farklı sorulardır.

4. Resolution is not the same as accuracy

Clock resolution is the nominal interval the clock can distinguish. You can inspect it with time.get_clock_info("perf_counter").resolution. A fine clock still has call overhead, and your program still experiences noise. Many displayed decimal places do not establish equally many trustworthy digits.

Suppose a disturbance adds 0.25 ms. On a 0.5 ms task, its share is 0.25/0.5 × 100 = 50%. On a 2-second task, first convert 2 seconds to 2000 ms. The share is 0.25/2000 × 100 = 0.0125%. Always use matching units before dividing.

Longer observations can reduce the relative effect of a fixed disturbance. However, disturbances are not all fixed, and very large inputs can introduce cache or memory effects. Use a small pilot experiment, increase sizes cautiously, and stop before an expensive trial becomes impractical. The lesson's “tens of milliseconds” advice is a practical starting point, not a universal mathematical threshold.

5. Tiny snippets and timeit

For a very short operation, time a batch of calls. If 1000 calls take total time t, the estimated average per call is t/1000. This is what timeit helps organize. Its standard configuration temporarily disables garbage collection during the timed work, which is helpful for some experiments but must be considered if collection is part of the workload you care about.

import timeit

def sum_formula(n):
    return n * (n + 1) // 2

assert sum_formula(1000) == 500500
totals = timeit.repeat(lambda: sum_formula(1000), number=1000, repeat=3)
print("Observed total seconds for each 1000-call batch:", totals)
print("Minimum batch average per call:", min(totals) / 1000)

The lambda supplies a tiny callable that performs the chosen call; it is not an extra algorithm to learn. The measured average includes calling overhead. This block has bounded inputs and produces real observations, with no promised numeric timing.

The loop and formula give the same sum because 1 + … + n = n(n+1)/2. At n = 4, the formula gives 4×5/2 = 10. The loop performs n additions; the formula performs a fixed number of arithmetic operations under the course's unit-cost model. For arbitrarily large Python integers, arithmetic costs grow with the number of bits, so “fixed number of operations” does not mean unlimited-size arithmetic is literally free.

6. Graduated practice with complete solutions

Practice 1 — make search reusable

Write contains(data, target) and explain why the final False must be outside the loop. Test [3, 9, 4] with targets 9 and 5, and test an empty list.

Solution 1

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

assert contains([3, 9, 4], 9) is True
assert contains([3, 9, 4], 5) is False
assert contains([], 9) is False
print("All three search cases passed.")

For target 9, comparing 3 is unsuccessful, but does not justify failure: later items remain. Only exhausting the list justifies False. The empty list immediately reaches that final return.

Practice 2 — repair a measurement report

A report times list construction, search, and printing together, then calls the result “search time.” It reports one run. Give a complete repair and calculate the average of illustrative repeats 18, 12, 12 ms.

Solution 2

Construct the list first, choose a missing target to require a full scan, warm up according to a stated policy, then time only the search. Repeat and move printing afterward. Preserve the individual observations. The example mean is (18+12+12)/3 = 14 ms; the minimum is 12 ms. State the statistic and measured scope. If construction is intentionally included, rename the result “construction plus search time” rather than claiming the observation is meaningless.

Practice 3 — check correctness before comparing speed

Compare the loop and formula for n = 0, 1, 4, 10. Predict the answers and explain why a timing win alone would not validate either implementation.

Solution 3

def loop_sum(n):
    result = 0
    for value in range(1, n + 1):
        result += value
    return result

def formula_sum(n):
    return n * (n + 1) // 2

for n, expected in [(0, 0), (1, 1), (4, 10), (10, 55)]:
    assert loop_sum(n) == formula_sum(n) == expected
    print(n, expected)

Both methods satisfy these checks. Returning zero immediately would be extremely fast but wrong for most inputs. Test cases support correctness; the summation identity explains why the formula works for all non-negative integers.

Misconceptions, glossary, and readiness

You are ready when you can trace sum_to(4), explain None, put a timer around search alone, and compute a repeat statistic with correct units. If returns are unclear, repair Practice 1 before timing. If percentages are unclear, redo the 0.25 ms example entirely in milliseconds. If measurements fluctuate, keep the samples and inspect scope before making a claim.

Bridge to Week 6: one timing answers “how long here?” Several input sizes answer “how does it change?” Bring the same function, correctness checks and measurement policy to the doubling experiment.

Be clear about what you time

First check that the function returns the right answer. Then decide which work to time. Put the timer around that work, and leave unrelated printing outside. Say whether preparing the input is part of the measurement.

Draw or trace. Draw setup → start timer → function call → stop timer → report. Mark whether creating the input is inside or outside the interval.

Predict before checking. If one method includes input construction and another reuses prepared data, can their timings alone establish which method answers a query faster?

Worked reasoning

No. The two timings include different work. Use the same input rules, check that the answers agree, and treat preparation the same way. Repeat the measurements because times vary. A tiny measured time does not mean no work happened. Reporting only the fastest convenient run hides that variation.

def loop_sum(n):
    total = 0
    for value in range(1, n + 1):
        total += value
    return total

for n in (0, 1, 7, 20):
    assert loop_sum(n) == n * (n + 1) // 2
print("Results agree on the checked inputs; timing comes next.")

Change one thing. Change the question from one query on ready-made data to the full task starting with raw input. Explain why the timing boundary must change.

Türkçe: Kronometre yalnızca içine aldığın işi ölçer. Aynı çıktıyı doğrula, hazırlık maliyetini belirt, sonra karşılaştır.

Additional analysis laboratory

Functions let us put a boundary around the work being measured. The boundary must match the claim. If the claim is about a complete method, setup belongs inside the function; if the claim is query-only, setup must be reported separately.

Extra exam-style prompt: A report says a lookup method takes O(1) because the timer starts after the set is built. What wording repairs the claim?

Solution: Say "After a set has already been built, each ordinary membership query is expected O(1) under the hash model." For the complete method, add the O(n) build cost and memory cost. If there are q queries, the total average model is O(n + q).

Turkce: Kronometrenin nerede baslayip bittigi iddianin siniridir. Hazirlik isini disarida biraktiysan, bunu acikca soylemeden tum algoritmayi olcmus sayilmazsin.