Algorithms

Empirical Time Complexity via the Leibniz Series

Measuring and plotting the running time of a Leibniz-series computation of π in order to observe linear time complexity as an empirical phenomenon rather than an asymptotic claim.

• Algorithms
• Big-O
• Complexity
• π
• Python
• Matplotlib

The Leibniz series

The Leibniz formula expresses π as an alternating infinite series:

π = 4·(1 − 1/3 + 1/5 − 1/7 + 1/9 − …)

Summing the first n terms requires a single loop that performs a constant amount of work per term, so the time required to compute the partial sum is linear in the number of terms, that is, O(n). The series is noted here only for its computational structure; it converges slowly and is not a practical method for obtaining π to high precision.

Method

Rather than computing the value of π alone, the running time of the computation is measured directly. For each n from 0 to 100,000, the partial sum is evaluated, the elapsed wall-clock time is recorded using time.perf_counter(), and the measured time is plotted against n. The resulting curve is an empirical trace of the algorithm’s time complexity.

for i in range(0, 100000):
    terms.append(i)
    start = time.perf_counter()
    calculate_pi(i)
    end = time.perf_counter()
    times.append(end - start)
    plt.plot(terms, times, color="red")
    plt.draw(); plt.pause(0.1)

Discussion

Time complexity is ordinarily presented as an analytical result. This project provides the complementary empirical view: a trace that is approximately linear in n is the observable signature of O(n) behaviour. The experiment also illustrates the practical caveats of benchmarking. Timing jitter, operating-system scheduling, and interpreter warm-up all introduce variance, so the measured curve is never perfectly clean. This variability is itself an instructive property of real performance measurement.