Big O notation — the common language of efficiency

Big O is the common language computer scientists everywhere use to answer one question: “When the data grows, will this code survive or melt?” Once you can read it, you can judge whether a solution scales — without running the program even once.

Core idea

Why do we count operations instead of measuring seconds?

Because seconds lie. A faster machine, a different language, or the system load at that moment all change the measured time. The same code might take 2 seconds on an old laptop but 0.2 seconds on a new one — and that number tells you nothing about the quality of the algorithm.

Big O does not care “how fast it is right now”; it cares “how much worse it gets as the data grows.”

So we measure the growth rate of the number of operations as the input size n approaches infinity (n → ∞), and two rules keep the analysis simple:

• Drop the constants: 2n becomes O(n), 500 becomes O(1), because constant factors stop mattering once n is huge.
• Keep only the fastest-growing term: n² + n + 100 becomes O(n²), because for large n the n² term dominates everything else.

What we get is the pure “shape of growth” — independent of any hardware or language.

The formal definition: why “dropping terms” is mathematically valid

This isn’t hand-waving — it rests on a precise definition (from CLRS Chapter 3): we say f(n) = O(g(n)) if there exist a positive constant c and a starting point n₀ such that

f(n) ≤ c · g(n)   for all n ≥ n₀

In plain words: “from some point onward (n₀), f(n) will never exceed g(n) scaled by some constant (c).”

Let’s actually prove one: let f(n) = 3n² + 5n + 2. We claim f(n) = O(n²).

For n ≥ 1, we always have 5n ≤ 5n² and 2 ≤ 2n², so

f(n) = 3n² + 5n + 2 ≤ 3n² + 5n² + 2n² = 10n²

Pick c = 10 and n₀ = 1 and we’re done — we’ve rigorously proven f(n) = O(n²) with no guessing involved. This is why dropping small terms and constants isn’t a shortcut; it’s a consequence provable from the definition itself.

Big O (O) is an upper bound, Big Omega (Ω) is a lower bound, and Big Theta (Θ) is when both bounds meet (a tight bound). This lesson focuses on O because “how bad can it get” is the most common question in practice — but if you see Θ(n log n) in a textbook, know that it’s more precise, since it pins down both the upper and lower bound.

The complexity zoo

This table runs from best to worst, with an intuition for how each “feels” when n = 1,000,000.

Notation	Name	Tangible example	n = 1,000,000 feels like…
O(1)	constant	indexing an array arr[i]	a single blink — same no matter how big the data is
O(log n)	logarithmic	binary search	~20 steps — like flipping through a dictionary
O(n)	linear	scanning a list for the max value	~1 million steps — very fast for a computer
O(n log n)	linearithmic	a good sort (merge sort, Timsort)	~20 million steps — still comfortable
O(n²)	quadratic	comparing every pair (nested loop)	~1 trillion steps — minutes to hours of grind
O(n³)	cubic	triple-nested loops, e.g. naive matrix multiplication	~10¹⁸ steps — beyond what today’s computers can chew through
O(2ⁿ)	exponential	trying every subset, naive recursive Fibonacci	the universe ends before it finishes

Rule of thumb: O(n²) starts to worry you when n reaches the tens of thousands, and O(2ⁿ) is only usable when n stays below ~40.

Play with all the growth curves interactively — toggle each one on and off to see who overtakes whom, and where:

Want to feel what O(n²) looks like in action? Watch bubble sort below — notice how the number of comparisons grows quadratically as the bars increase:

Best, average, and worst case

Think about digging for your keys in a bag. Some days your hand lands on them first try (lucky). Some days you have to dump the whole bag out (unlucky). The same algorithm can have “lucky days” and “unlucky days” too, depending on how the input happens to be arranged.

Take insertion sort:

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        while j >= 0 and arr[j] > key:  # shift bigger elements right
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key
    return arr

• Best case: the array is already sorted → arr[j] > key is false immediately, so the while loop never runs → O(n)
• Worst case: the array is reverse-sorted → every new element has to shift past everything already inserted → O(n²)
• Average case: random order → each element shifts past roughly half of what’s already inserted → still O(n²) (a smaller constant than worst case, but the same order)

Case	Happens when	Insertion Sort	Quicksort (first-element pivot)
Best	Data already sorted / pivot splits the data evenly	O(n)	O(n log n)
Average	Random data	O(n²)	O(n log n)
Worst	Data reverse-sorted / already-sorted data plus the worst possible pivot choice	O(n²)	O(n²)

When someone says “this algorithm is O(n log n)” without specifying a case, the default computer scientists mean is the worst case, because it’s the safest upper bound guarantee. Quicksort has a reputation for speed, but if the input is already sorted and the pivot choice is naive, it’s just as bad as bubble sort.

Space complexity

If time complexity tells you “how long it takes,” space complexity tells you “how much workspace it needs to spread out while running.” Some algorithms use a constant amount of space no matter what; others need to store more as n grows.

Example — iterative sum:

def sum_all(arr):
    total = 0            # a single variable, no matter how long arr is
    for x in arr:
        total += x
    return total

It only ever uses one extra variable, total, regardless of how many elements arr has → O(1) space.

Example — recursive factorial:

def factorial(n):
    if n == 0:
        return 1
    return n * factorial(n - 1)

Every time the function calls itself, the system has to keep a call stack frame around waiting for the result. The recursion depth equals n → O(n) space, even though the function never creates a single large data structure.

Function	Time	Auxiliary space
sum_all (iterative)	O(n)	O(1)
factorial (recursive)	O(n)	O(n) — call stack
binary search (iterative)	O(log n)	O(1)
binary search (recursive)	O(log n)	O(log n) — call stack
merge sort	O(n log n)	O(n) — temporary array for merging

Rule of thumb: if the code calls itself (recursion), always count the recursion depth as memory used — no matter how little each individual frame holds. This is the trap beginners overlook most often.

Amortized analysis: why dynamic arrays still “feel” like O(1)

Think of saving money for a rainy day: most days you pay a little, and only occasionally does a big expense show up. But averaged over the whole year, the cost per day stays low and predictable.

Python’s list.append() works the same way. Normally it’s O(1), but under the hood a list is backed by a fixed-size array. When that array fills up, Python has to allocate a new, larger array (typically double the size) and copy every existing element into it — an O(n) operation. So is .append() really O(1)?

Let’s trace the cost of each append call as the capacity doubles every time it fills up:

append #	Prior capacity	Resize needed?	Cost (copy + insert)	Cumulative cost
1	0	grow to 1	0 + 1 = 1	1
2	1	grow to 2	1 + 1 = 2	3
3	2	grow to 4	2 + 1 = 3	6
4	4	no	1	7
5	4	grow to 8	4 + 1 = 5	12
6–8	8	no	1 each	15
9	8	grow to 16	8 + 1 = 9	24

The average cost per append after 9 calls = 24 / 9 ≈ 2.67 — a constant, not something that grows with n.

General proof (the aggregate method): the total copying cost across all resizes is 1 + 2 + 4 + ... + n < 2n (a geometric series), plus the cost of the n inserts themselves. Total: at most 3n across all n appends. Dividing by n gives a constant per operation → O(1) amortized.

“Amortized” does not mean “every single call is fast” — an individual append can genuinely be O(n) when it triggers a resize. But averaged across a sequence of n operations, the total cost never exceeds O(n), which averages out to O(1) per operation. This is why list.append() in Python and ArrayList in Java are called O(1) amortized, not O(1) on every single call.

Reading Big O from code

You do not need to memorize — just look at the structure with five rules:

• Sequential steps = add them, then keep the biggest term
• Nested loops = multiply
• Halving the problem each round = log
• Two unequal control variables (n and m) stay separate — don’t assume nested loops always mean n²
• Recursion: write it as a recurrence relation, then solve it with a recursion tree or the Master Theorem

Example 1 — single loop → O(n)

def find_max(nums):
    biggest = nums[0]
    for x in nums:        # runs n times
        if x > biggest:
            biggest = x
    return biggest

One loop over the data → O(n)

Example 2 — loop inside a loop → O(n²)

def has_duplicate(nums):
    for i in range(len(nums)):       # n times
        for j in range(i + 1, len(nums)):  # ~n times
            if nums[i] == nums[j]:
                return True
    return False

Outer loop times inner loop = n × n → O(n²)

Example 3 — halving each round → O(log n)

def binary_search(sorted_nums, target):
    lo, hi = 0, len(sorted_nums) - 1
    while lo <= hi:                  # range shrinks by half each round
        mid = (lo + hi) // 2
        if sorted_nums[mid] == target:
            return mid
        elif sorted_nums[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

Each round throws away half the data → O(log n). Trace it step by step yourself:

Example 4 — sequential → add, keep the biggest term

def process(nums):
    total = 0
    for x in nums:        # O(n)
        total += x
    nums.sort()           # O(n log n)
    return total, nums

O(n) + O(n log n) = O(n log n), because we keep only the fastest-growing term.

Example 5 — two unequal variables → don’t collapse them into one

def print_matrix(rows, cols):
    for r in range(rows):        # n times (one per row)
        for c in range(cols):    # m times (one per column)
            print(r, c)

The outer loop runs once per row, the inner loop once per column — these are two different quantities, so it’s O(rows × cols), or O(n · m). It is not O(n²) unless rows == cols. A common mistake is jumping straight to “nested loops = n²” without first checking what each loop’s control variable actually counts.

Example 6 — recursion → write it as a recurrence

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])    # T(n/2)
    right = merge_sort(arr[mid:])   # T(n/2)
    return merge(left, right)       # O(n) — merges two sorted lists via two pointers

Write the cost as a recurrence: T(n) = 2T(n/2) + O(n) — split the problem into two halves, then combine at a cost of O(n). Drawing this as a recursion tree, there are log n levels of depth, and each level does O(n) total work (since the data is split but never lost) → overall O(n) × O(log n) = O(n log n).

Real-world problem

Imagine a “find duplicate user emails” feature. The team writes this and tests it on their own machine with n = 100 users — instant. It passes review and ships to production.

def find_duplicate_emails(users):
    duplicates = []
    for i in range(len(users)):
        for j in range(i + 1, len(users)):
            if users[i].email == users[j].email:
                duplicates.append(users[i].email)
    return duplicates

This is O(n²). At n = 100 that means ~5,000 comparisons — snappy. But when the user base grows to n = 10,000,000, it becomes ~50 trillion comparisons. The server stalls, requests time out, users stare at a spinner.

The fix: use a hash set to remember emails you’ve seen, dropping it to O(n).

def find_duplicate_emails(users):
    seen = set()
    duplicates = []
    for u in users:           # one pass
        if u.email in seen:   # O(1) lookup
            duplicates.append(u.email)
        else:
            seen.add(u.email)
    return duplicates

Lesson: code that “works” on small test data can hide an O(n²) time bomb. Reading Big O is your armor before things blow up in production.

Exercises

State the Big O complexity of each snippet.

1

def first_element(arr):
    return arr[0]

Answer

O(1) — a single index access, independent of the size of arr.

2

def sum_all(arr):
    total = 0
    for x in arr:
        total += x
    return total

Answer

O(n) — one loop over the elements.

3

def print_pairs(arr):
    for a in arr:
        for b in arr:
            print(a, b)

Answer

O(n²) — nested loops, each running n times → n × n.

4

def count_down(n):
    while n > 1:
        print(n)
        n = n // 2

Answer

O(log n) — n is halved every round, so the number of rounds equals log base 2 of n.

5

def mystery(arr):
    arr.sort()                 # part A
    for x in arr:              # part B
        for y in arr:
            if x == y:
                break

Answer

Part A is O(n log n) and part B is O(n²). They run sequentially, so we add them: O(n log n) + O(n²) = O(n²), because n² grows faster.

6

def cartesian_print(a, b):
    for x in a:
        for y in b:
            print(x, y)

Suppose a has n elements and b has m elements, where n does not equal m. What is the complexity?

Answer

O(n · m) — the outer loop runs over a (n times), the inner loop over b (m times). They aren’t the same quantity, so this is not O(n²) unless len(a) == len(b).

7

Consider insertion_sort from earlier in the lesson. State its time complexity in the best case and worst case for input [5, 4, 3, 2, 1] versus [1, 2, 3, 4, 5].

Answer

[1, 2, 3, 4, 5] is already sorted → best case O(n) (the while loop never runs).

[5, 4, 3, 2, 1] is fully reverse-sorted → worst case O(n²) (every new element has to shift past everything already inserted).

8

def sum_recursive(arr):
    if not arr:
        return 0
    return arr[0] + sum_recursive(arr[1:])

This function returns the correct sum, but analyze both its time and space complexity carefully. (Hint: arr[1:] creates a brand-new list every time.)

Answer

Space: the recursion depth equals n → O(n) space from the call stack.

Time: at first glance it looks like O(n) since it makes n calls, but arr[1:] is itself a list copy costing O(k), where k is the remaining length. Summed up: n + (n-1) + (n-2) + ... + 1 = O(n²). This is a classic trap — code that “looks like” O(n) but actually hides an O(n²) from list slicing.

9

Explain why Python’s list.append() is called O(1) amortized, even though resizing the underlying array occasionally requires copying every element (an O(n) operation). If you perform n appends in a row, what is the total cost, and what is the average cost per call?

Answer

Resizing (doubling capacity) only happens at sizes 1, 2, 4, 8, ..., n — not on every call. The total copying cost across all resizes is 1 + 2 + 4 + ... + n < 2n (a geometric series), plus the cost of the n inserts themselves. Total: at most 3n across all n appends. Dividing by n gives a constant → O(1) amortized, even though an individual call can genuinely be O(n).

10

def binary_search_buggy(arr, target):
    lo, hi = 0, len(arr)
    while lo < hi:
        mid = (lo + hi) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            lo = mid
        else:
            hi = mid
    return -1

This code has a serious bug hiding in it. Find it, then explain what happens to the complexity if it’s left unfixed.

Answer

The bug is on the line lo = mid — it should be lo = mid + 1 when arr[mid] < target. Otherwise, once hi - lo == 1, mid always equals lo, so lo never moves, and the loop runs forever (an infinite loop).

Big O theory assumes an algorithm actually terminates. This buggy version doesn’t terminate in some cases, so you can’t even talk about its Big O. Once fixed with lo = mid + 1, it goes back to being O(log n) as expected. The lesson: Big O only measures correct algorithms — before analyzing complexity, make sure you’ve read carefully enough to confirm the code is actually correct.

AI Code Critique

Suppose you give an AI assistant this prompt:

“Write a Python function that takes two lists of numbers and returns a list of the numbers that appear in both lists.”

And the AI replies with this correct code:

def common_elements(a, b):
    result = []
    for x in a:
        for y in b:
            if x == y and x not in result:
                result.append(x)
    return result

Question: the answer is right, but what is its complexity, and what happens when each list has a million elements?

Spot the efficiency flaw, then write a follow-up prompt such as:

“This is O(n²). Please rewrite it as O(n) using a set.”

Solution and fix

The original is O(n²) (actually worse — x not in result is itself O(n), pushing the worst case toward O(n³)). With a million elements it becomes unusably slow.

The fix is a set, which checks membership in O(1) time:

def common_elements(a, b):
    set_b = set(b)            # O(n)
    return list({x for x in a if x in set_b})  # O(n)

Total O(n) — vastly faster on large data.

AI is great at “writing correct code,” but it often picks the most straightforward approach, not the most scalable one — so the job of judging is still yours.

🎮 Game Dev: frame-budget math for collision detection

A 60 FPS game gives you about 16.67 ms per frame to do everything — input, AI, physics, collision, rendering — before the screen has to update again. Big O tells you exactly how a system’s per-frame cost grows as entity count n climbs, which means you can predict, before you ever profile, whether “checks every pair of entities” is going to eat your whole frame budget once the level gets crowded.

Worked example — naive pairwise collision vs. a spatial grid:

def naive_collision_checks(entities):
    """O(n^2): compare every pair of entities once."""
    checks = 0
    n = len(entities)
    for i in range(n):
        for j in range(i + 1, n):
            checks += 1
            # here you'd call collides(entities[i], entities[j])
    return checks


def grid_collision_checks(entities, cell_size=64):
    """O(n) on average: only compare entities inside the same grid cell."""
    buckets = {}
    for e in entities:
        key = (e["x"] // cell_size, e["y"] // cell_size)
        buckets.setdefault(key, []).append(e)

    checks = 0
    for bucket in buckets.values():        # far fewer entities per bucket
        m = len(bucket)
        checks += m * (m - 1) // 2          # only pairs *within the same cell*
    return checks

The naive version runs n(n-1)/2 checks no matter where entities are — classic O(n²). The grid version buckets entities by position first (O(n)) and then only compares entities sharing a cell. If entities are spread roughly evenly across the world, each bucket stays small and roughly constant in size as n grows, so total checks scale close to O(n) instead of O(n²).

Now put a number on “blows the budget.” Say your collision system gets a slice of the frame — about 2 ms — and each pairwise check (a simple AABB or circle overlap test) costs roughly 50 ns. That’s a budget of 2 ms / 50 ns ≈ 40,000 checks per frame. Solving n(n-1)/2 ≈ 40,000 gives n ≈ 283 — past roughly 280 entities, the naive O(n²) loop alone burns through more than your entire collision budget, before physics or rendering even start. The grid version, doing close to O(n) work, could handle tens of thousands of entities in the same 2 ms.

Figure: comparisons per frame vs. entity count N. The naive O(n²) curve crosses the 16 ms budget line around N ≈ 280 and keeps climbing; the spatial-grid O(n) curve barely rises in the same range.

Try it live — this widget runs both approaches at increasing entity counts and counts comparisons in real time:

Exercises

Game 1

def update_particles(particles):
    for i in range(len(particles)):
        for j in range(len(particles)):
            if i != j:
                apply_repulsion(particles[i], particles[j])

What’s the Big O of one frame of this loop? Using the ~40,000-check budget from above, at roughly what N does this drop below 60 FPS?

Answer

It’s O(n²) — for every particle it scans all others, so it’s n × (n-1) ≈ n² calls per frame (note: this counts every ordered pair, i.e. twice the unordered-pair count from the worked example). Setting n² ≈ 40,000 gives n ≈ 200. Past roughly 200 particles, this loop alone exceeds the frame’s collision budget, and the game starts dropping below 60 FPS.

Game 2

def move_entities(entities, dt):
    for e in entities:
        e["x"] += e["vx"] * dt
        e["y"] += e["vy"] * dt

What’s the Big O here? Does this ever threaten the 16 ms budget, even at n = 100,000?

Answer

O(n) — one constant-time update per entity, no nested loop. Even at n = 100,000, that’s 100,000 cheap arithmetic updates, which is nowhere near the millions of operations a 16 ms budget can absorb at typical CPU speeds. Linear per-frame work almost never blows the budget on its own; quadratic work is what does.

Game 3

The spatial grid in the worked example assumes entities are spread out evenly. What happens to its complexity if every entity clusters into a single grid cell (e.g., a huge crowd standing on one tile)?

Answer

It degrades to O(n²) — if all n entities land in one bucket, grid_collision_checks computes m * (m-1) // 2 for a bucket of size m = n, which is exactly the naive pairwise count. The grid only helps when entities are actually distributed across cells; worst-case clustering removes the benefit entirely. This is why real engines pick cell size relative to entity size/spread and sometimes fall back to finer subdivision (quadtrees) when a cell gets overloaded.

Game 4

A sweep-and-prune broad phase sorts entities by their x-coordinate once per frame (O(n log n)), then only checks pairs whose x-ranges overlap in the sorted order (typically O(n) more checks for reasonably spread-out entities). What’s the overall Big O per frame, and why is this usually safe at 60 FPS even for n in the thousands?

Answer

Overall it’s O(n log n) — the sort dominates, since O(n log n) + O(n) keeps only the fastest-growing term. Because log n grows extremely slowly (log₂(10,000) ≈ 13), the total work for n = 10,000 is on the order of 130,000 operations — comfortably inside a millisecond-scale budget, unlike the trillion-scale blowup of O(n²) at the same n. This is why sweep-and-prune (and spatial grids) are the standard answer to “collision detection got slow” in production engines.

Challenge problems

Challenge 1 — budgeting a bullet-hell

You’re building a bullet-hell shooter with up to 2,000 bullets and 50 enemies on screen simultaneously. Collision checks (bullets vs. enemies, bullets vs. player) must fit inside a 3 ms slice of the 16 ms frame budget. Sketch an approach, and justify why naive all-pairs checking would fail here.

Approach

All-pairs checking is 2,050 × 2,049 / 2 ≈ 2.1 million comparisons per frame — at even 20 ns per check that’s ~42 ms, more than double the entire frame budget, let alone the 3 ms slice. A workable design: bucket bullets and enemies into a spatial grid sized to roughly the bullet’s collision radius, and only test bullets against enemies (and vice versa) sharing or bordering a cell — skip bullet-vs-bullet entirely since bullets don’t collide with each other. Since enemies (50) are few, you could also just loop enemies × bullets-in-nearby-cells rather than building a full grid for enemies. The key move is recognizing you don’t need O((bullets+enemies)²) — you need O(bullets) lookups against a small, spatially-filtered enemy set.

Challenge 2 — the profiler doesn’t lie

Your profiler shows the collision pass taking 12 ms at n = 800 entities using the naive O(n²) loop, blowing your 16 ms budget on its own. You switch to the spatial grid from the worked example and it drops to 0.4 ms. Estimate roughly how large n could grow before the grid version itself risks exceeding a 2 ms collision budget — and name one real-game scenario that would defeat the grid’s O(n) assumption even at moderate n.

Approach

If the grid keeps bucket sizes roughly constant, checks scale close to O(n), so cost per entity stays roughly what it was at 800 entities (0.4 ms / 800 ≈ 0.0005 ms/entity). A 2 ms budget then supports roughly 2 / 0.0005 ≈ 4,000 entities — an order of magnitude more headroom than the naive version’s ~280-entity ceiling from the worked example. But that assumes even spread: a scenario like a “boss room” where all entities crowd around one target, or a stampede/flocking mechanic where units cluster tightly, pushes many entities into a few cells and drags the grid back toward O(n²) behavior locally — exactly the clustering failure from Game 3 above.

Going deeper

• MIT 6.006 Introduction to Algorithms — lecture notes on complexity analysis (MIT OpenCourseWare): https://ocw.mit.edu/courses/6-006-introduction-to-algorithms-spring-2020/
• Stanford CS161 Design and Analysis of Algorithms — material on asymptotic notation: https://stanford-cs161.github.io/winter2024/
• CLRS — Introduction to Algorithms, Chapter 3 “Growth of Functions” — the standard reference for the rigorous definitions of Big O, Ω, and Θ; read it to see the proofs behind this lesson.
• Sedgewick & Wayne — Algorithms, 4th ed. — has a detailed analysis of “resizing arrays” (the exact same mechanism we traced above) with Java code that maps directly onto Python’s dynamic lists.
• Roughgarden — Algorithms Illuminated, Vol. 1: The Basics — explains asymptotic notation in the most approachable language of any of these books; a great on-ramp before tackling CLRS.
• Big-O Cheat Sheet — a summary table of complexities for popular data structures and algorithms: https://www.bigocheatsheet.com/