Complexity and Big-O in practice

Reading growth rates off real loops, measuring instead of guessing, and knowing where Big-O stops predicting runtime.

Reading cost off the code

Big-O describes how the work grows as the input grows, ignoring constants and lower-order terms. It is a statement about the shape of the curve, not about milliseconds: a nested loop over ten items is still O(n²), and it is still instant.

# O(1): a fixed number of steps whatever n is
def first(items):
    return items[0] if items else None

# O(n): one pass; going through the data twice is O(2n) = O(n)
def total(nums):
    running = 0
    for x in nums:
        running += x
    return running

# O(n^2): the inner loop runs about n times per outer iteration
def has_duplicate_slow(items):
    for i in range(len(items)):
        for j in range(i + 1, len(items)):
            if items[i] == items[j]:
                return True
    return False

# O(n) time, O(n) extra space: buy speed with memory
def has_duplicate_fast(items):
    seen = set()
    for x in items:
        if x in seen:
            return True
        seen.add(x)
    return False

# O(log n): the range of the loop halves each step
def count_bits(n):
    bits = 0
    while n:
        n //= 2
        bits += 1
    return bits

for i in range(n):        # n
    for j in range(n):    # x n      -> O(n^2)
        work()

for i in range(n):
    for j in range(i, n): # n + (n-1) + ... + 1 = n(n+1)/2, still O(n^2)
        work()

i = 1
while i < n:              # i doubles, so log2(n) steps -> O(log n)
    i *= 2

for x in items:           # outer n, inner log n -> O(n log n)
    j = 1
    while j < n:
        j *= 2

# Sequential blocks add, nested blocks multiply
setup()                   # O(n)
for x in items:           # O(n)
    pass
# total: O(n), not O(n^2)

• Drop constants and lower-order terms: O(3n + 20) is O(n).
• Sequential sections add and you keep the largest; nested sections multiply.
• A loop over a halving or doubling counter is logarithmic, which is why binary search and balanced trees are cheap.
• Recursion costs O(branches ^ depth) unless you memoise; naive Fibonacci is O(2ⁿ) while memoised is O(n).
• Amortised analysis explains dynamic arrays: most appends are O(1) and the occasional resize is O(n), so the average is O(1).

Growth rates you can feel

import time
import random

def timeit(fn, data, repeats=3):
    best = float('inf')
    for _ in range(repeats):
        start = time.perf_counter()
        fn(data)
        best = min(best, time.perf_counter() - start)
    return best

data = [random.random() for _ in range(1000)]
print('total   ', round(timeit(total, data), 5))
print('dupes   ', round(timeit(has_duplicate_fast, data), 5))

# Confirm the shape of the curve, not the wall-clock number
for n in (1000, 2000, 4000):
    sizes = list(range(n))
    print(n, round(timeit(lambda d: has_duplicate_slow(d[:400]), sizes), 5))

Where Big-O stops predicting

import bisect

# Both are O(n log n) sorts, but the built-in is C and wins by a wide margin
items = [random.random() for _ in range(1_000_000)]
sorted(items)                      # built-in Timsort
# a hand-written merge sort in Python would be 50x slower on the same input

# Searching a sorted list: O(log n) probes, but each probe is a Python call
idx = bisect.bisect_left(sorted_items, target)

# A set lookup is O(1) *in the hash*, but a bad hash turns it into O(n)
# and cache misses on a large dict can make a linear scan of a small array win

• Big-O hides constants. An O(n) loop written in Python can lose to an O(n log n) routine written in C, and usually does.
• Cache locality is invisible to Big-O. A contiguous array scan often beats a linked structure with a better theoretical bound.
• The input distribution matters: quicksort is O(n log n) on random data and O(n²) on sorted data with a naive pivot.
• Space counts too. Reading a 4 GB table into memory to get O(1) lookups fails for reasons no time complexity measures.
• Use the bound to reject an algorithm that cannot scale, then measure to choose between the candidates that can.

FAQ

Related

Sorting and searching Trees and choosing a structure

Last refreshed 2026-09-18.