Big-O in Python: Timing O(1), O(n), and O(n^2) for Real

Fri Aug 14 2026

Big-O describes how an algorithm’s work grows as input size n grows. This post times three functions with different Big-O shapes on the same input sizes and looks at what the growth actually does to runtime.

The code

import time


def constant_time(data):
    # O(1): one lookup, no matter how big data is
    return data[0]


def linear_time(data):
    # O(n): touches every element once
    total = 0
    for x in data:
        total += x
    return total


def quadratic_time(data):
    # O(n^2): nested loop over data, work grows with n*n
    count = 0
    for x in data:
        for y in data:
            if x == y:
                count += 1
    return count


def timeit(fn, data):
    start = time.perf_counter()
    fn(data)
    return time.perf_counter() - start


sizes = [500, 1000, 2000, 4000]

print(f"{'n':>6} | {'O(1)':>10} | {'O(n)':>10} | {'O(n^2)':>10}")
for n in sizes:
    data = list(range(n))
    t_const = timeit(constant_time, data)
    t_linear = timeit(linear_time, data)
    t_quad = timeit(quadratic_time, data)
    print(f"{n:>6} | {t_const:>10.6f} | {t_linear:>10.6f} | {t_quad:>10.6f}")

Each function runs against the same data list at four sizes (500, 1000, 2000, 4000), and timeit wraps each call with time.perf_counter() to measure real elapsed seconds.

Running it

Actual run, real timings in seconds:

     n |       O(1) |       O(n) |     O(n^2)
   500 |   0.000001 |   0.000010 |   0.002113
  1000 |   0.000001 |   0.000017 |   0.008253
  2000 |   0.000000 |   0.000033 |   0.033541
  4000 |   0.000000 |   0.000066 |   0.135899

constant_time stayed at effectively zero across all four sizes, since it only ever reads data[0]. linear_time roughly doubled each time n doubled: 0.000010 -> 0.000017 -> 0.000033 -> 0.000066. quadratic_time roughly quadrupled each time n doubled: 0.002113 -> 0.008253 -> 0.033541 -> 0.135899, and by n=4000 it dwarfs the other two entirely.

Takeaway

Same input sizes, three different growth patterns in the actual timings: flat for O(1), a doubling pattern for O(n), and a quadrupling pattern for O(n^2) as n doubled each step.