How fast? Big O notation

At a billion steps per second, an n² method on a million values takes about 17 minutes; an n log n method takes 0.02 seconds.

Growth matters more than the exact count

So far we have counted steps exactly: 45 comparisons, 4 swaps, 20 checks. Exact counts are useful for small examples, but they depend on details such as whether bubble sort stops early or how a pivot is chosen. When the input becomes large, one thing dominates everything else: how the count grows as n grows. An algorithm whose steps grow like n² will eventually lose to one whose steps grow like n log n, however carefully the first one is tuned.

Big O notation is the shorthand for that growth. Writing that an algorithm is O(n²), read "big O of n squared", means that for large n its step count is at most some constant times n². Two rules make it easy to use. Drop constant factors: 3n and n/2 are both O(n). Keep only the fastest-growing term: n²/2 − n/2, the comparisons of selection sort, is O(n²), because for large n the n² part is almost all of it. MIT's 6.006 course uses the same idea when it compares data structures and sorts by their asymptotic running time.

The common growth rates

• O(1), constant. The work does not depend on n: reading the first value of a list, or a value at a known position.
• O(log n), logarithmic. Each step halves the problem: binary search. A million values, about 20 steps.
• O(n), linear. Each value is handled once: linear search, finding the largest value, adding up a list.
• O(n log n). Merge sort, and quicksort on average. The best that comparison sorting can do.
• O(n²), quadratic. Every pair is looked at: bubble, selection and insertion sort in the worst case, or two loops nested inside each other.
• O(2ⁿ), exponential. The work doubles with every extra value: trying every subset of n items, or moving n disks in the Tower of Hanoi.

What the numbers mean in seconds

Suppose a computer does a billion (10⁹) basic steps per second, a fair round figure for one processor core. Here is what each growth rate means for a million values. O(log n) is about 20 steps, far under a microsecond. O(n) is a million steps, one millisecond. O(n log n) is about 20 million steps, 0.02 seconds. O(n²) is 10¹² steps, a thousand seconds, about 17 minutes. O(2ⁿ) cannot be finished: 2 to the power of a million is a number with more than 300,000 digits. This is why choosing the right algorithm usually matters far more than buying a faster computer. A machine ten times faster turns 17 minutes into 1.7 minutes; switching from O(n²) to O(n log n) turns it into a fiftieth of a second.

Reading Big O from code

You can often read the growth rate straight from the shape of the code. A single loop over the list is O(n). Two loops, one inside the other, both over the list, are O(n²): for each of the n outer rounds the inner loop does up to n rounds. A loop that halves a number each time, such as while (n > 1) n = Math.floor(n / 2), is O(log n): starting from 1,000 it runs 9 times, from a million 19 times. Steps that happen one after another add up, and the bigger term wins: an O(n) loop followed by an O(n²) loop is O(n²) overall.

// O(n): one pass
let total = 0;
for (const x of list) total += x;

// O(n²): every pair
for (let i = 0; i < list.length; i++)
  for (let j = i + 1; j < list.length; j++)
    if (list[i] === list[j]) console.log("duplicate", list[i]);

// O(log n): halving
let k = list.length, rounds = 0;
while (k > 1) { k = Math.floor(k / 2); rounds++; }

Best, average and worst case

One algorithm can behave very differently on different inputs. Insertion sort is O(n) on a list that is already sorted and O(n²) on a reversed one. Quicksort is O(n log n) on average and O(n²) with consistently bad pivots. When people quote a single Big O figure without saying which case, they usually mean the worst case, because it is a guarantee: the algorithm will never do worse. Big O also leaves things out. It ignores constant factors, so for small inputs an O(n²) method with very simple steps can beat an O(n log n) one. That is why many real sorting routines switch to insertion sort for short pieces of the list.