Experiments spanning input sizes

Intermediate Asymptotics & empirical timing

Created by Pavel · 29.04.2026 at 19:08 UTC

Asymptotic claims are about limits; empirical curves show where limits matter for your hardware and constants. A standard exercise: double n a few times, measure runtime, plot log-log or semi-log. A line on log-log with slope 2 suggests quadratic growth; slope 1 suggests linear.

Sampling noise and setup effects mean you should not trust a single timing at one n. Sweep sizes, warm up, fix random seeds when algorithms are randomized, and record environment (Python version, BLAS, machine load).

In coursework, tabulate milliseconds vs n for a naive vs vectorised implementation—the crossover often surprises students.

Matplotlib gallery (plotting timings): [1].

Sources

[1]https://matplotlib.org/stable/gallery/index.html Return to text

University approvals: 0

Tasks

Question 1

Why benchmark at several values of n instead of a single large run?

Hint

Trends need multiple points.

CPython forbids multiple n

Scaling behaviour and crossover points only show up across a range

print() works once per interpreter only

Big-O requires exactly three data points

Question 2

On a log-log plot of runtime T(n) vs n, a straight line with slope ≈2 most strongly suggests:

Hint

Power law: log T ≈ k log n + const with k≈2.

O(log n)

O(n)

O(n²)

O(1)

Question 3

geo_sizes(limit_exp) returns [10**3, 10**4, ..., 10**limit_exp] inclusive. Example: geo_sizes(5)[-1] == 10**5.

Hint

Exponent range starts at 3.

def geo_sizes(limit_exp: int):
    pass

Starter code is prefilled; replace TODO blocks with your solution.

Runtime output (stdout/stderr)

2 test cases will be used for grading

Run checks runtime behavior only. Final correctness is evaluated when you submit.

Card Info

Topic: Asymptotics & empirical timing
Difficulty: Intermediate
Completed: 0 users

Creator

Pavel