Big-O Notation, Minus the Fear

Big-O has a reputation problem. It arrives wrapped in limit notation and Greek letters, so people assume it's calculus. It isn't. Big-O answers one question, and you already ask it every time you write a loop:

If the input gets 10× bigger, how much slower does this get?

That's it. Everything else is vocabulary.

What Big-O actually measures

Big-O describes how the work grows as the input grows. Not how fast your laptop is, not what language you wrote it in, just the shape of the growth curve. Two programs can differ by a factor of 50 in raw speed and still have the same Big-O, because Big-O deliberately ignores constant factors. It's a tool for comparing algorithms, not benchmarks.

Concretely: if an algorithm is O(n), doubling the input roughly doubles the work. If it's O(n²), doubling the input roughly quadruples the work. At n = 100 nobody can tell the difference. At n = 10,000,000 one of them finishes and the other one gets your service paged.

The five classes you actually meet

There are infinitely many complexity classes. In practice you will spend your whole career meeting the same five. Anchor each one to a thing you already know:

Sit with that last row. A million squared is a trillion. A modern CPU does on the order of a billion simple operations per second, so O(n²) at n = 10⁶ is not "a bit slow". It's fifteen minutes versus a blink. This is why interviewers care: the gap between classes isn't a tuning problem, it's a "does this finish today" problem.

O(1): constant. The work doesn't depend on input size at all. Looking up a key in a hash map, indexing into an array, pushing onto a stack. One million entries or ten, same cost.

O(log n): logarithmic. Each step halves the remaining problem. Binary search is the canonical example: to find a name in a sorted list of a million entries, you need about 20 comparisons, because 2²⁰ ≈ 1,000,000. Logarithms are absurdly flat. Doubling n adds one step.

O(n): linear. You touch every element once (or a fixed number of times). Summing an array, finding a max, the one-pass hash map solution to Two Sum.

O(n log n): linearithmic. The signature of good comparison sorting (merge sort, and what your language's built-in sort achieves). Also the cost of "sort first, then do something linear", a hugely common pattern.

O(n²): quadratic. The signature of "for each element, look at every other element." Brute-force Two Sum. Fine for small n, radioactive at scale.

Why constants get dropped

Big-O says O(3n + 40) is just O(n). This feels like cheating until you see why: as n grows, the dominant term eats everything else.

Take f(n) = n² + 100n. At n = 10, the 100n term dominates (1,000 vs 100) and you might think "the linear part matters more." At n = 10,000, the n² term is 100,000,000 and the 100n term is 1,000,000, a rounding error. Big-O is a statement about large n, and at large n only the fastest-growing term matters. Same reason the base of the log doesn't matter: log₂ n and log₁₀ n differ by a constant factor (~3.3), and constants are exactly what we agreed to ignore.

One honest caveat: constants do matter in real engineering. An O(n) algorithm with a huge constant can lose to an O(n log n) one at every input size you'll ever see. Big-O tells you which algorithm wins eventually. Profiling tells you which wins today. Use both.

How to eyeball a loop nest

You don't derive complexity with equations. You read the loops.

Rule 1: sequential work adds, and the bigger term wins.

def stats(nums):
    total = sum(nums)          # O(n)
    biggest = max(nums)        # O(n)
    return total, biggest      # O(n) + O(n) = O(n)

Rule 2: nested loops over the same input multiply.

function hasDuplicatePair(nums) {
  for (let i = 0; i < nums.length; i++) {        // n iterations
    for (let j = i + 1; j < nums.length; j++) {  // up to n each
      if (nums[i] === nums[j]) return true;
    }
  }
  return false; // n * n/2 comparisons on average => O(n²)
}

The inner loop shrinking (j = i + 1) doesn't save you. It averages n/2 iterations, and n · n/2 is still O(n²). Halving is a constant. Constants drop.

Rule 3: a loop that halves is a log.

def binary_search(sorted_nums, target):
    lo, hi = 0, len(sorted_nums) - 1
    while lo <= hi:                    # halves the range each pass
        mid = (lo + hi) // 2
        if sorted_nums[mid] == target:
            return mid
        if sorted_nums[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1                          # O(log n)

Rule 4: only count loops that scale with the input. A loop that runs exactly 26 times (one per letter) is O(1), no matter how scary it looks.

The trap to avoid: two loops in sequence are O(n), not O(n²). Multiplication is only for nesting.

Amortized cost, in one paragraph

Some operations are cheap almost always and expensive rarely, on a schedule that guarantees the expensive ones stay rare. Appending to a dynamic array is the classic case: usually O(1), but occasionally the array is full and must be copied into a bigger one, O(n) for that single append. Because the array doubles when it grows, a copy of size n only happens after n cheap appends have "paid into the meter," so the average cost per append across any long sequence is O(1). That average-with-a-guarantee is called amortized O(1). It is not "average case" hand-waving. It's a hard bound on the total. We'll see the mechanics up close in the next lesson.

What to remember

• Big-O answers one question: how does work grow as input grows?
• Five classes cover almost everything: O(1), O(log n), O(n), O(n log n), O(n²).
• Constants and lower-order terms drop because the dominant term eats them at scale, but constants still matter when you profile real code.
• Read loops, don't derive equations: sequential adds, nested-over-the-same-input multiplies, halving means log, fixed-count loops are O(1).
• n = 10⁶ makes the classes visceral: O(n²) is a trillion operations; O(log n) is twenty.