Algorithm Complexity — Big-O Intuition

By the end of this lesson you can:

• Name the common complexity classes: O(1), O(log n), O(n), O(n log n), O(n²), O(2ⁿ).
• Look at a function and guess its Big-O.
• Predict roughly how big an input each class can handle in one second.
• Pick a faster algorithm when the slow one would blow up.

The fastest way to understand a function's Big-O: double the input. See what happens to the time.

When N doubles, the runtime…

stays the same           →  O(1)         constant
goes up by 1             →  O(log n)     logarithmic
doubles                  →  O(n)         linear
slightly more than 2x    →  O(n log n)   linearithmic
quadruples               →  O(n²)        quadratic
goes up 8x               →  O(n³)        cubic
SQUARES                  →  O(2ⁿ)        exponential — bad

O(1) · Constant

Takes the same time regardless of input size. Read a known dict key, access a list by index, push onto a stack.

def first(lst):
    return lst[0]            # O(1) — single index

def get_age(person):
    return person["age"]     # O(1) — dict lookup

O(log n) · Logarithmic

Time grows slowly. Doubling N adds just one comparison. Binary search is the classic.

def binary_search(lst, target):
    # ... halve the search space each step ...
    # O(log n) — 20 steps for 1 million items

O(n) · Linear

One pass over the data. Linear search, sum, max, the in operator.

def total(lst):
    s = 0
    for x in lst:            # one pass — O(n)
        s += x
    return s

# Or: sum(lst), max(lst), len([x for x in lst if ...])

O(n log n) · Linearithmic

Slightly more than linear. Good sorts (Timsort, mergesort, heapsort) live here.

def average_then_sort(lst):
    avg = sum(lst) / len(lst)        # O(n)
    return sorted(lst)               # O(n log n) — dominates

O(n²) · Quadratic

Nested loop. Bubble sort, insertion sort, naïve pair-finding.

def has_duplicate_naive(lst):
    for i in range(len(lst)):
        for j in range(i + 1, len(lst)):    # nested loop
            if lst[i] == lst[j]:
                return True
    return False
# O(n²) — N=10000 takes seconds

Better:

def has_duplicate_fast(lst):
    return len(set(lst)) != len(lst)        # O(n)

Same problem, two complexity classes. Algorithm choice matters more than micro-optimisation.

O(2ⁿ) · Exponential

Naïve recursive Fibonacci, brute-force subset enumeration. The danger zone.

def fib(n):
    if n < 2: return n
    return fib(n - 1) + fib(n - 2)
# O(2ⁿ) — fib(40) is already slow.

How big a list can each handle in 1 second?

Class           N you can handle in 1 second on a laptop
                (very rough — depends on the constant)

O(1)            unlimited
O(log n)        ~1 quintillion (10¹⁸)
O(n)            ~100 million
O(n log n)      ~10 million
O(n²)           ~5,000-10,000
O(n³)           ~500
O(2ⁿ)           ~30
O(n!)           ~10

The pattern: each step down the table caps the manageable N at a much smaller value. If your data could have a million items, you need at most O(n log n).

Worst case vs average case vs amortised

Big-O usually refers to worst case. Some operations have a worse worst case but better amortised cost — like appending to a Python list (occasionally has to resize, but on average O(1)). For now: think worst-case unless told otherwise.

Reading a function

Quick rules:

• One loop over the input → O(n)
• Two nested loops → O(n²)
• Halving the input each step → O(log n)
• Calling a sort inside → at least O(n log n)
• Recursive doubling branch (no memo) → O(2ⁿ)
• Indexing/dict/set membership → O(1)

The "find a pair that sums to k" problem, solved three ways. Save as two_sum.py:

# two_sum.py — same answer, three complexities

import random, time


def two_sum_naive(lst, target):
    """O(n²) — check every pair."""
    for i in range(len(lst)):
        for j in range(i + 1, len(lst)):
            if lst[i] + lst[j] == target:
                return (i, j)
    return None


def two_sum_sorted(lst, target):
    """O(n log n) — sort then two-pointer."""
    indexed = sorted(enumerate(lst), key=lambda p: p[1])
    lo, hi = 0, len(indexed) - 1
    while lo < hi:
        s = indexed[lo][1] + indexed[hi][1]
        if s == target:
            i, j = sorted([indexed[lo][0], indexed[hi][0]])
            return (i, j)
        if s < target:
            lo += 1
        else:
            hi -= 1
    return None


def two_sum_hash(lst, target):
    """O(n) — hash table single pass."""
    seen = {}
    for i, x in enumerate(lst):
        if target - x in seen:
            return (seen[target - x], i)
        seen[x] = i
    return None


# Race
N = 5000
random.seed(0)
data = random.sample(range(N * 10), N)
target = data[10] + data[200]                   # guaranteed to exist

for name, fn in [
    ("naive O(n²)",   two_sum_naive),
    ("sorted O(n log n)", two_sum_sorted),
    ("hash O(n)",     two_sum_hash),
]:
    start = time.perf_counter()
    fn(data, target)
    elapsed = (time.perf_counter() - start) * 1000
    print(f"  {name:<20} {elapsed:>8.2f} ms")

Sample output

  naive O(n²)         1450.00 ms
  sorted O(n log n)     2.50 ms
  hash O(n)             1.10 ms

Read the diff

Same answer. Three orders of magnitude difference. The naïve version is ~1300× slower than the hash version. At N=50,000 the naïve takes 2+ minutes; the hash version is still under 100ms. This is why Big-O matters.

For each function below, decide its Big-O. Cover the answers and try first.

def f1(lst):
    return lst[0]                            # ?

def f2(lst):
    return sum(lst)                          # ?

def f3(lst):
    return sorted(lst)                       # ?

def f4(lst):
    for x in lst:
        for y in lst:
            print(x, y)                       # ?

def f5(lst):
    for x in lst:
        if x in lst:                          # ← in on a list is O(n)
            print(x)
# Big-O?

def f6(lst):
    s = set(lst)
    for x in lst:
        if x in s:                            # ← in on a set is O(1)
            print(x)
# Big-O?

def f7(n):
    while n > 0:
        n //= 2
# Big-O?

def f8(n):                    # naive fib
    if n < 2: return n
    return f8(n - 1) + f8(n - 2)

def f9(lst):
    while len(lst) > 1:
        lst = lst[::2]              # take every 2nd element
    return lst[0]

def f10(lst):
    while len(lst) > 1:
        mid = len(lst) // 2
        f10(lst[:mid])
        lst = lst[mid:]

Big-O describes how runtime grows with input size. Common classes from fastest to slowest: O(1), O(log n), O(n), O(n log n), O(n²), O(n³), O(2ⁿ), O(n!). Constants don't matter; the curve shape does. Each step down dramatically caps the manageable input size — past O(n²), N=10,000 is already painful. The fastest way to identify an algorithm's class: double the input and see what happens to the time. Algorithm choice usually matters more than language-level optimisation.