The Few You Actually Meet

There are infinitely many possible growth shapes, but you don't need them. In day-to-day code, the same small cast shows up over and over. Learn these five and you can name the Big-O of most things you'll ever read.

For each one, hold the question from Phase 1 in your head: double the input - what happens to the work?

⏭️ New here? If n and "how work grows" feel fuzzy, read Phase 1 first - it's short, and the rest of this builds on it.

O(1) - constant: "doesn't care how big the data is"

What it is. The work stays the same no matter how much data you have - double the input, make it a billion, the code does the same fixed amount of work. Grabbing an item by index, reading a hash-map value, checking if a number is even: none of these care about size.

A real example.

def first_item(items):
    return items[0]

What just happened: items[0] jumps straight to the first element whether items has 5 entries or 5 million. No looping, no searching - that's O(1).

Why this saves you later. Once something is O(1), stop worrying about it scaling - these are the lookups you want in hot paths. A big part of writing fast code is turning expensive scans into O(1) lookups (more in Phase 3).

O(n) - linear: "twice the data, twice the work"

What it is. The work grows in lockstep with the input - touch every item once, double the input and you do twice the work. A straight, plain line.

What it does in real life. Looping through a list to sum numbers, find the biggest one, print each row, or search an unsorted list. If you have to look at everything, you're at least O(n).

A real example.

def total(numbers):
    running = 0
    for n in numbers:        # ← visits each number exactly once
        running += n
    return running

What just happened: The loop runs once per element - 1,000 numbers means 1,000 additions. Work tracks input one-to-one, and for "I need to see everything," that's the best you can do.

Why this saves you later. O(n) is usually fine - it's the baseline cost of reading your data. Watch not for a single loop but a loop inside another loop, which is next.

O(n²) - quadratic: the nested-loop trap

What it is. For every item, you do work proportional to all the items - a loop inside a loop. Double the input and the work quadruples. This is the handshake-at-a-party shape from Phase 1, and it's the one that quietly kills programs.

What it does in real life. Comparing every item to every other item: checking a list for duplicates the naive way, computing the distance between every pair of points, the classic bubble sort.

A real example.

def has_duplicate(items):
    for i in range(len(items)):          # ← outer loop: n times
        for j in range(i + 1, len(items)):   # ← inner loop: ~n times each
            if items[i] == items[j]:
                return True
    return False

What just happened: The inner loop walks much of the rest of the list for each item. With 1,000 items that's roughly a million comparisons; with a million items, a trillion. Two stacked loops over the same data is the visual signature of O(n²).

⚠️ Gotcha: the nested loop you didn't notice. The dangerous version isn't two obvious for loops. It's a loop that calls something which itself loops - like if x in big_list: inside a for loop, where in quietly scans the whole list every time. It looks like one loop. It behaves like two. When you see a search, a .index(), or an in check inside a loop, stop and ask whether you've accidentally built O(n²). (This exact trap gets its own story in Phase 3.)

Why this saves you later. Most "it was instant in testing and now production hangs" disasters are an accidental O(n²). Spotting the nested-loop shape is one of the highest-value habits in this guide.

O(log n) - logarithmic: "halve the problem each step"

What it is. Each step throws away half of what's left, so even gigantic inputs collapse to a tiny number of steps - doubling the input adds just one more step.

What it does in real life. The flagship example is binary search: find a value in a sorted list by repeatedly checking the middle and discarding the half that can't contain it. A balanced search tree works the same way.

A real example. Searching a sorted phone book of a million names:

   1,000,000 names → check the middle → keep half →   500,000
                                                  →   250,000
                                                  →   125,000
                                                  →    ... and so on
   after ~20 halvings → 1 name left.

What just happened: Each check halves the search space - a million entries found in about 20 steps, two million in about 21. That's why O(log n) lines look almost flat, barely rising no matter how far right you go.

📝 Terminology. A logarithm sounds like math homework, but here it means exactly one homely thing: how many times can I halve this before I hit 1? That count is the log. No calculator required.

Why this saves you later. When a lookup is too slow, turn an O(n) scan into an O(log n) search - usually by keeping the data sorted or indexed. Binary search gets its own full walkthrough, off-by-one bugs included, in Sorting & Searching, Explained.

O(n log n) - the shape of good sorting

What it is. You do a linear amount of work (n), but each piece involves a halving-style log n cost - so you multiply them. Noticeably more than O(n), dramatically better than O(n²) - think of it as "linear, with a small, well-behaved tax."

What it does in real life. This is the speed of every good general-purpose sort - merge sort, heapsort, and the sorts built into real languages. sorted() in Python and .sort() in JavaScript both pay O(n log n).

A real example.

names = ["Ada", "Linus", "Grace", "Alan", "Margaret"]
ordered = sorted(names)   # ← the built-in sort: O(n log n)

What just happened: Sorting requires comparing and moving items relative to each other, not just looking at each once. Good sorts do that in O(n log n) instead of the O(n²) of comparing every pair

• for a million items, twenty million steps versus a trillion.

Why this saves you later. O(n log n) is the practical ceiling for "I need everything in order." About to hand-roll a sort with nested loops (O(n²))? Stop - the built-in sort is almost always faster and already O(n log n). And once data is sorted, you unlock that lovely O(log n) binary search.

Name it from the code

This is your cheat-card. When you're staring at code, match the pattern to the shape:

⚠️ Read it as the worst path, and drop the small stuff. Big-O describes the worst case - so two separate loops one after the other is still O(n) (it's 2n, but Big-O drops constant multipliers - see Phase 3). What flips you to a worse shape is nesting - work happening per item, for every item.

Recap

1. O(1) - same work regardless of size; the lookups you want everywhere.
2. O(n) - touch everything once; the plain baseline.
3. O(n²) - a loop inside a loop; double the data, quadruple the work; the trap.
4. O(log n) - halve each step; gigantic inputs in a handful of steps (binary search).
5. O(n log n) - the speed of good sorting; far better than O(n²).
6. The fastest way to spot trouble: a search or loop nested inside another loop.

Next, why this isn't academic - the same code that's fine at 100 items and dies at 10 million, and how your choice of data structure secretly sets your Big-O.

Watch it animated: Big O notation

← Phase 1: It's About How Things GROW · Guide overview · Phase 3: Why It Matters in Real Life →

See it grow

Drag n and watch how each complexity class pulls away from the others: