Big O Complexity Analysis — Deep Dive

Formal definition and practical meaning

Big O notation formally states: f(n) = O(g(n)) if there exist constants c > 0 and n₀ such that f(n) ≤ c·g(n) for all n ≥ n₀. Translation: once the input gets large enough, f(n) grows no faster than g(n), up to a constant multiplier.

This is an upper bound. When we say an algorithm is O(n²), we mean it grows no faster than n² — it could be faster. Big Theta (Θ) provides a tight bound. In practice, most engineers use O to mean Θ, and that is fine for interviews and code reviews.

CPython data structure complexity reference

List (dynamic array)

CPython’s list is a contiguous array of pointers. It over-allocates by a growth factor of roughly 1.125x to make appends amortized O(1).

import sys

lst = []
prev = sys.getsizeof(lst)
for i in range(100):
    lst.append(i)
    curr = sys.getsizeof(lst)
    if curr != prev:
        print(f"Length {len(lst):3d}: {curr} bytes (grew by {curr - prev})")
        prev = curr

Operation	Average	Worst	Notes
lst[i]	O(1)	O(1)	Pointer arithmetic
lst.append(x)	O(1)*	O(n)	Amortized; resize copies
lst.insert(i, x)	O(n)	O(n)	Shifts elements
lst.pop()	O(1)	O(1)	End removal
lst.pop(0)	O(n)	O(n)	Shifts all elements
x in lst	O(n)	O(n)	Linear scan
lst.sort()	O(n log n)	O(n log n)	Timsort
lst[a:b]	O(b-a)	O(b-a)	Creates new list
lst.extend(other)	O(k)	O(n+k)	k = len(other)

Dict (hash table)

CPython 3.6+ dicts maintain insertion order using a compact hash table with separate dense storage for key-value pairs.

Operation	Average	Worst	Notes
d[key]	O(1)	O(n)	Hash collision chain
d[key] = val	O(1)	O(n)	May trigger resize
key in d	O(1)	O(n)	Same as lookup
del d[key]	O(1)	O(n)	Marks as deleted
len(d)	O(1)	O(1)	Stored counter
d.keys()	O(1)	O(1)	View object
Iteration	O(n)	O(n)	Over dense array

The worst case O(n) from hash collisions is near-impossible with CPython’s hash randomization (PYTHONHASHSEED). In practice, treat dict operations as O(1).

Set (hash table without values)

Same complexity as dict for membership, insertion, and deletion.

Operation	Average	Notes
x in s	O(1)	Hash-based
s.add(x)	O(1)	May resize
s & t	O(min(m,n))	Intersection
s | t	O(m+n)	Union
s - t	O(m)	Difference

Deque (doubly-linked blocks)

collections.deque uses blocks of 64 pointers linked together, giving O(1) operations at both ends.

Operation	Average	Notes
dq.append(x)	O(1)	Right end
dq.appendleft(x)	O(1)	Left end
dq[i]	O(n)	Not contiguous
x in dq	O(n)	Linear scan

Amortized analysis: why append is O(1)

When a list runs out of allocated space, CPython allocates a new array roughly 12.5% larger and copies everything over. That copy is O(n). But it happens so rarely relative to the number of appends that the cost spreads out.

import time

def benchmark_appends(n):
    """Demonstrate amortized O(1) for list.append."""
    lst = []
    start = time.perf_counter()
    for i in range(n):
        lst.append(i)
    elapsed = time.perf_counter() - start
    return elapsed

# If append were O(n) amortized, doubling n would quadruple time
# If O(1) amortized, doubling n roughly doubles time
for exp in range(5, 8):
    n = 10 ** exp
    t = benchmark_appends(n)
    print(f"n={n:>10,}: {t:.4f}s  ({t/n*1e6:.2f} µs/append)")

The proof uses the banker’s method: charge each append 3 coins instead of 1. Two extra coins are banked. When a resize happens (copying n elements), the n banked coins pay for the copy. Total cost across n appends: 3n, so amortized cost per append is O(1).

Empirical verification with timeit

Theory is nice. Measurement is better. Here is how to verify complexity claims:

import timeit
import random

def measure_lookup(container_type, sizes):
    """Measure membership test scaling."""
    results = []
    for n in sizes:
        data = list(range(n))
        random.shuffle(data)
        container = container_type(data)
        target = random.randint(0, n - 1)

        # Time 10,000 lookups
        t = timeit.timeit(lambda: target in container, number=10_000)
        results.append((n, t))
        print(f"  n={n:>8,}: {t:.4f}s for 10k lookups")
    return results

sizes = [1_000, 10_000, 100_000, 1_000_000]

print("List (expected O(n) per lookup):")
measure_lookup(list, sizes)

print("\nSet (expected O(1) per lookup):")
measure_lookup(set, sizes)

Expected output pattern: list lookup time grows 10x when n grows 10x (linear). Set lookup time stays roughly flat (constant). This empirical evidence confirms the theoretical complexity.

The O(n²) trap in Python

The most common performance bug in Python code:

# O(n²) — linear search inside a loop
def find_duplicates_slow(items):
    seen = []
    duplicates = []
    for item in items:
        if item in seen:          # O(n) scan each time
            duplicates.append(item)
        seen.append(item)
    return duplicates

# O(n) — hash-based lookup inside a loop
def find_duplicates_fast(items):
    seen = set()
    duplicates = []
    for item in items:
        if item in seen:          # O(1) lookup each time
            duplicates.append(item)
        seen.add(item)
    return duplicates

With 100,000 items, the slow version takes ~8 seconds. The fast version takes ~15 milliseconds. Same result, 500x faster.

Complexity of common Python patterns

String concatenation

# O(n²) — each += creates a new string
result = ""
for chunk in chunks:
    result += chunk  # copies all previous content each time

# O(n) — join pre-allocates
result = "".join(chunks)

CPython has an optimization that makes += sometimes O(1) when the string has a reference count of 1, but this is an implementation detail you should not rely on.

Sorting with key functions

# O(n log n) — key function called once per element, then cached
sorted(items, key=lambda x: x.lower())

# O(n² log n) — DO NOT do this (comparison function called n log n times,
# each potentially expensive)
import functools
sorted(items, key=functools.cmp_to_key(lambda a, b: complex_compare(a, b)))

Generator pipelines

# O(1) space — processes one item at a time
total = sum(x * x for x in range(10_000_000))

# O(n) space — materializes entire list
total = sum([x * x for x in range(10_000_000)])

Recursion depth and stack space

Recursive algorithms consume O(depth) stack space. Python’s default recursion limit is 1,000. A naive recursive Fibonacci is O(2ⁿ) time and O(n) space. With memoization it drops to O(n) time and O(n) space. An iterative version achieves O(n) time and O(1) space.

# O(2ⁿ) time — exponential explosion
def fib_naive(n):
    if n <= 1:
        return n
    return fib_naive(n - 1) + fib_naive(n - 2)

# O(n) time, O(n) space — memoized
from functools import lru_cache

@lru_cache(maxsize=None)
def fib_memo(n):
    if n <= 1:
        return n
    return fib_memo(n - 1) + fib_memo(n - 2)

# O(n) time, O(1) space — iterative
def fib_iter(n):
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b
    return a

Interview complexity analysis framework

When analyzing code in an interview, follow this checklist:

1. Identify the input variable(s): What is n? Sometimes there are two inputs (m and n).
2. Count loop nesting: Each nested loop that depends on n multiplies complexity.
3. Check for hidden iterations: in, index(), count(), string slicing, list slicing.
4. Check for recursion: Draw the recursion tree. Count nodes (time) and depth (space).
5. Identify the dominant term: O(n² + n log n) = O(n²).
6. State both time and space: An O(n) time algorithm that builds an n×n matrix uses O(n²) space.

Practice: analyze this code

def mystery(nums):
    n = len(nums)
    result = []
    for i in range(n):                    # O(n)
        for j in range(i + 1, n):         # O(n) in worst case
            if nums[i] + nums[j] == 0:
                result.append((i, j))
    return result

Time: O(n²) — the inner loop runs n-1, n-2, …, 1 times, totaling n(n-1)/2 iterations. Space: O(k) where k is the number of pairs found. In the worst case k = O(n²).

When Big O is not enough

Big O ignores constant factors, and in Python those constants can be large. CPython’s interpreter overhead means a C extension running an O(n log n) algorithm often beats pure Python running an O(n) algorithm. NumPy’s vectorized operations exploit this: even though numpy.sum(arr) and a Python for loop are both O(n), NumPy can be 100x faster because the loop runs in compiled C.

Cache locality also matters. A list of integers in NumPy (contiguous memory) traverses much faster than a Python list of int objects (pointer chasing). Same Big O, very different wall-clock time.

Profile before optimizing. python -m cProfile script.py reveals where time actually goes. Sometimes the O(n²) function is called on 50 items and takes microseconds, while the O(n) function processes millions and dominates runtime.

One thing to remember: Big O is your first filter — it catches algorithms that cannot scale. But real performance depends on constants, cache behavior, and Python’s interpreter overhead. Measure both the theoretical complexity and the actual runtime.