sdlc.dev

Data structures and algorithms path · Cost and memory · Topic 1 of 13

Big-O in practice

Not started

Big-O notation describes how the work an algorithm does grows as its input grows. O(1) means the cost doesn't depend on the input size, O(n) means it grows in step with it, O(n²) means doubling the input quadruples the work. It is a statement about the shape of the curve, not about speed, so it is most useful for asking "what happens at 100 times the data?" and least useful for choosing between two things with the same shape.

Why it matters: It is the quickest way to tell whether code that is fine on 100 rows will fall over on 10 million, as long as you remember what it hides.

  1. 1Growth, not speed

    O(n) says the work grows in proportion to the input. It says nothing about how long one step takes.

  2. 2Keep the biggest term

    3n² + 50n + 7 is O(n²). For large inputs the largest term dominates and constant factors are dropped.

  3. 3Constants still matter

    Memory layout, allocation and cache misses can make an O(n) structure several times slower than another O(n) structure.

  4. 4Say which case

    Worst case, average case and amortised cost can differ. A hash lookup is O(1) on average and O(n) in the worst case.

1

How it works

The explanation, with examples you can run.

Counting steps

The notation comes from counting the basic steps an algorithm takes in terms of the input size n, then keeping only the fastest-growing term. Here are three loops side by side:

⌘/Ctrl + Enter
OutputNot run yet

Press Run to see what your code prints, in order.

Runs in this browser, in an isolated frame with no access to this page. console.log, info, warn and error are shown; code runs as a classic script, so use an async function for await.

At n = 1000 the halving loop runs 9 times, the single loop 1,000 times and the nested loop a million times. That gap only widens. The common classes, from cheapest to most expensive, are O(1), O(log n) (halving: binary search, balanced trees), O(n) (one pass), O(n log n) (good sorting), O(n²) (comparing every pair) and O(2ⁿ) (trying every subset).

Formally, f(n) is O(g(n)) if f(n) ≤ c·g(n) for some constant c once n is large enough. That makes Big-O an upper bound; people usually mean the tight bound (Θ) when they say it, and this path does too.

What the notation hides

Constant factors. O(n) with a cheap step and O(n) with an expensive step are the same class. A loop over a JavaScript array of numbers and a loop over a linked list of the same numbers are both O(n), but the array is read from consecutive memory that the CPU prefetches into cache, while each list node can sit anywhere and costs a separate memory fetch. On real hardware that difference is easily several times, and in the linked lists topic, with nodes scattered across the heap, it is close to a hundred.

Small n. For small inputs a "worse" algorithm with tiny constants often wins. Production sorting routines switch to insertion sort, which is O(n²), for short runs for exactly this reason.

Memory. Big-O is usually quoted for time. An algorithm that is fast but needs O(n) extra memory, such as merge sort, may be the wrong choice when n is a billion rows.

Which case. Quicksort is O(n log n) on average but O(n²) in the worst case. A hash table lookup is O(1) on average but O(n) when every key collides. Appending to a dynamic array is O(n) when it has to grow, but amortised O(1), meaning the total cost of n appends is O(n). Always ask which of these a claim is about.

Using it well

Use Big-O to rule things out early: a nested loop over two tables of a million rows each is a trillion steps, whatever language you write it in. Then measure the candidates that survive, with realistic data sizes, because constants, caches and the shape of real data decide the rest.

2

Check yourself

3 questions. Get them all right to finish this topic.

  1. 1.An O(n log n) function takes 1 second for a million items. Roughly how long for two million?
  2. 2.Which loop is O(log n)?
    for (let i = 0; i < n; i++) {}          // Afor (let i = n; i > 1; i = Math.floor(i / 2)) {}   // Bfor (let i = 0; i < n * n; i++) {}      // C
  3. 3.Two algorithms are both O(n). Can one still be ten times faster than the other?

0 of 3 right so far. Get all three to finish this topic.

Go deeper