Inventing Big O Notation

sum_list grows ~5× when n grows 5× (from 1,000 to 5,000). has_pair_with_sum grows ~25×. One grows proportionally to n, the other proportionally to n².

for n in [1000, 5000, 10000]:
    lst = list(range(n))

    start = time.time()
    sum_list(lst)
    t1 = time.time() - start

    start = time.time()
    has_pair_with_sum(lst, -1)
    t2 = time.time() - start

    print(f"n={n}  sum_list: {t1:.4f}s  has_pair: {t2:.4f}s")

sum_list is nearly flat — barely above zero. has_pair_with_sum curves upward steeply. One grows linearly, the other quadratically.

times_sum = []
times_pair = []
for n in sizes:
    lst = list(range(n))
    start = time.time()
    sum_list(lst)
    times_sum.append(time.time() - start)
    start = time.time()
    has_pair_with_sum(lst, -1)
    times_pair.append(time.time() - start)

plt.figure(figsize=(8, 5))
plt.plot(sizes, times_sum, 'o-', label='sum_list')
plt.plot(sizes, times_pair, 's-', label='has_pair_with_sum')
plt.xlabel('Input size (n)')
plt.ylabel('Time (seconds)')
plt.legend()
plt.title('How does time grow with input size?')
plt.grid(True, alpha=0.3)
plt.show()

sum_list: count = n exactly. has_pair: count/n² ≈ 0.5 regardless of n. The quadratic function does about n²/2 operations.

def sum_list_counted(lst):
    count = 0
    total = 0
    for x in lst:
        total += x
        count += 1
    return total, count

def has_pair_counted(lst, target):
    count = 0
    for i in range(len(lst)):
        for j in range(i + 1, len(lst)):
            count += 1
            if lst[i] + lst[j] == target:
                return True, count
    return False, count

for n in [10, 100, 1000]:
    lst = list(range(n))
    _, c1 = sum_list_counted(lst)
    _, c2 = has_pair_counted(lst, -1)
    print(f"n={n}  sum_list: {c1}  has_pair: {c2}  has_pair/n²: {c2/n**2:.3f}")

count/n² stays constant at ~0.5. This tells us the count grows proportionally to n².

The ÷2 is just a constant multiplier — it makes everything exactly half as much work, but the growth rate is the same. Whether it's n², n²/2, or 7n², the count still quadruples when n doubles. The shape of growth is what matters, not the exact count.

The ratio stays roughly constant. Both functions are "linear" — they grow at the same rate. The constant multiplier doesn't change the growth family.

def work_n(lst):
    s = 0
    for x in lst:
        s += x
    return s

def work_3n(lst):
    s = 0
    for x in lst:
        s += x
        s += x
        s += x
    return s

for n in [10000, 100000, 1000000]:
    lst = list(range(n))
    start = time.time(); work_n(lst); t1 = time.time() - start
    start = time.time(); work_3n(lst); t2 = time.time() - start
    print(f"n={n}  work_n: {t1:.4f}s  work_3n: {t2:.4f}s  ratio: {t2/t1:.1f}x")

The count grows as $\log_2(n)$ — logarithmic growth. Doubling the input adds just one more step. This is spectacularly slow growth.

for n in [10, 100, 1000, 10000, 100000]:
    lst = list(range(n))
    steps = halving_search_counted(lst, -1)
    print(f"n={n:>6}  steps: {steps}")

• 1 (always the same): Constant
• log(n): Logarithmic
• n: Linear
• n × log(n): Sometimes called "linearithmic" — between linear and quadratic
• n²: Quadratic

1. $5n + 3$ → n
2. $2n^2 + 10n + 7$ → n²
3. $100$ → 1 (constant — doesn't grow)
4. $n^3 + 1000n^2$ → n³
5. $3n\log n + 5n$ → n·log(n)

Any consistent notation works! You might have written ~n², Growth(n²), [n²], or something else entirely.

The standard notation used by computer scientists is O(n²) — the letter O followed by the growth term in parentheses. The O stands for "Order of" — as in "the order of growth."

The hierarchy is clear: $O(1) < O(\log n) < O(n) < O(n \log n) < O(n^2)$. At n = 100, O(n²) = 10,000 while O(n) = 100 — a 100× difference that only gets worse as n grows.

plt.figure(figsize=(8, 6))
plt.plot(n, np.ones_like(n), '-', linewidth=2, label='O(1)')
plt.plot(n, np.log2(n), '-', linewidth=2, label='O(log n)')
plt.plot(n, n, '-', linewidth=2, label='O(n)')
plt.plot(n, n * np.log2(n), '-', linewidth=2, label='O(n log n)')
plt.plot(n, n**2, '-', linewidth=2, label='O(n²)')
plt.xlabel('n')
plt.ylabel('Operations')
plt.legend()
plt.title('The Big O Hierarchy')
plt.grid(True, alpha=0.3)
plt.show()

O(n) — one loop through n items.

Total = $2n$. Big O = O(n). Two separate (non-nested) loops are still linear — the constant 2 drops away.

O(n²) — a loop inside a loop over n items.

O(1) — constant time. One index lookup, no loop.

max/n stays at 1.00. pairs/n² stays at ~0.50. Predictions confirmed.

def find_max_counted(lst):
    count = 0
    best = lst[0]
    for x in lst:
        count += 1
        if x > best:
            best = x
    return best, count

def all_pairs_counted(lst):
    count = 0
    for i in range(len(lst)):
        for j in range(i + 1, len(lst)):
            count += 1
    return count

import math
for n in [100, 1000, 10000]:
    lst = list(range(n))
    _, c_max = find_max_counted(lst)
    c_pairs = all_pairs_counted(lst)
    print(f"n={n}  max/n={c_max/n:.2f}  pairs/n²={c_pairs/n**2:.4f}")

• Best case: 1 comparison — target is at index 0. This is O(1).
• Worst case: n comparisons — target is last or missing. This is O(n).
• Average case: n/2 comparisons — still O(n) since we drop the ½.

Big O without qualification usually means worst case — it's a guarantee. "This algorithm is O(n)" means it will never take more than proportional-to-n time, no matter what input you give it.

• A: 1 variable → O(1) space — constant, regardless of n
• B: n items → O(n) space — grows linearly
• C: n × n items → O(n²) space — grows quadratically

elements/n stays at 1.0 for lists → O(n) space. elements/n² stays at 1.0 for matrices → O(n²) space. Same Big O idea, applied to memory instead of time.

print("List (n items):")
for n in [10, 100, 1000, 10000]:
    lst = list(range(n))
    print(f"  n={n:>5}  elements: {len(lst):>10}  elements/n: {len(lst)/n}")

print("\nMatrix (n*n items):")
for n in [10, 50, 100, 200]:
    mat = [[0] * n for _ in range(n)]
    total_items = sum(len(row) for row in mat)
    print(f"  n={n:>3}  elements: {total_items:>10}  elements/n^2: {total_items/n**2}")

Which is "better"? It depends. If you have a billion items and limited RAM, the O(1) space approach might be your only option (even though it's slow). If speed matters and you have memory to spare, the set wins easily.

This is the time–space tradeoff — one of the most fundamental tensions in computer science. Faster algorithms often use more memory, and memory-efficient ones are often slower. There's rarely a free lunch.

At $n = 10^9$: O(n) takes about 17 minutes. O(n²) takes 31,710 years.

O(1), O(log n), and O(n) are practical at any scale. O(n log n) is fine for billions. O(n²) is only viable for thousands. This is why Big O matters — it's the difference between "runs on my laptop" and "outlives the sun."

for n in [10, 1000, 10**6, 10**9]:
    print(f"n = {n:,}")
    print(f"  O(1)      = {human_time(1)}")
    print(f"  O(log n)  = {human_time(math.log2(n))}")
    print(f"  O(n)      = {human_time(n)}")
    print(f"  O(n lg n) = {human_time(n * math.log2(n))}")
    print(f"  O(n^2)    = {human_time(n ** 2)}")
    print()