Introduction

You cannot prove asymptotic time complexity experimentally, but you can gather strong evidence about how runtime grows as input size increases. The key is to measure carefully, vary input size systematically, and separate algorithmic growth from noise caused by hardware, caching, and benchmark setup.

What Experiments Can and Cannot Tell You

Theory gives a machine-independent growth class such as O(n log n) or O(n^2). Experiments give observed runtimes on one implementation, one machine, and one workload.

That makes experiments useful for:

• checking whether the implementation behaves roughly as expected
• comparing constants between algorithms
• spotting hidden costs or pathological cases

But experiments do not replace proofs. A curve that looks quadratic for the tested range is still only evidence, not a formal guarantee.

Benchmark Over Increasing Input Sizes

The basic method is to run the algorithm on a sequence of input sizes and measure the time for each one.

1import random
2import time
3
4def benchmark(fn, sizes, repeats=5):
5    results = []
6    for n in sizes:
7        samples = []
8        data = [random.randint(0, 10**6) for _ in range(n)]
9        for _ in range(repeats):
10            start = time.perf_counter()
11            fn(list(data))
12            end = time.perf_counter()
13            samples.append(end - start)
14        results.append((n, min(samples)))
15    return results
16
17def example_sort(values):
18    values.sort()
19
20print(benchmark(example_sort, [1000, 2000, 4000, 8000]))

Using multiple sizes is essential. One timing at one input size tells you almost nothing about growth.

Use Repeats and a Stable Timing Policy

Raw timing is noisy. Operating-system scheduling, background processes, cache effects, and interpreter warmup all distort single measurements.

That is why benchmarks should:

• repeat each case several times
• use a high-resolution timer such as time.perf_counter()
• summarize with a stable statistic such as the median or minimum

The minimum is often useful for algorithm experiments because it approximates the least-interfered-with run. The median is useful when noise is unavoidable and you want a more conservative view.

Look at Ratios, Not Just Raw Times

Suppose you double n. If the runtime roughly doubles, that suggests near-linear behavior over the tested range. If it grows by about four times, that suggests quadratic behavior. These ratio checks are often more informative than staring at absolute times.

Plotting also helps. A log-log plot or ratio table can make the growth pattern much easier to see than a simple list of numbers.

Control the Input Distribution

Experimental complexity depends on the data you feed the algorithm. Sorting random arrays, nearly sorted arrays, and reverse-sorted arrays can produce very different timings for the same algorithm.

So the experiment should state:

• what input family was used
• whether the input was random or adversarial
• whether each run reused or regenerated data

This matters because an algorithm may have different best-case, average-case, and worst-case behavior.

Avoid Benchmarking Mistakes

If the operation is very fast, loop overhead and object creation can dominate the measurement. In Python especially, generating the input may cost more than the algorithm under test if you are not careful.

A good benchmark isolates the algorithm itself:

• prepare input outside the timed region when appropriate
• copy mutable input if the algorithm changes it
• keep unrelated logging and printing outside the timed code

Otherwise you end up measuring the harness rather than the algorithm.

Common Pitfalls

• Trying to infer asymptotic class from a single timing.
• Ignoring input distribution and testing only one easy case.
• Including setup costs inside the timed region without realizing it.
• Trusting one noisy run instead of repeated measurements.
• Treating experimental evidence as a mathematical proof of complexity.

Summary

• Experimental testing can support, but not prove, a time-complexity claim.
• Measure runtime across many input sizes, not just one.
• Repeat runs and use stable timing statistics.
• Control the input family so the experiment matches the question you care about.
• Compare growth patterns and ratios, not just raw seconds.