Charts · 09

Big O, in the keystroke

Big O is the shape of how work grows with input, and in an interface you meet it as the search box that starts lagging behind your fingers once the list gets long. Type into both fields below: they do the same job on the same list, and one of them has a single line that is quadratic. Then the classes themselves, to scale, and what each costs at a billion operations a second, which is the number that decides whether a feature ships.

What it feels like

selected.includes(id) O(n · m)

type to measure

16 ms, one frame100 ms, feels instant

    selectedSet.has(id) O(n)

    type to measure

    16 ms, one frame100 ms, feels instant

      Same list, same query, same render. The only difference is one line: an array includes walks the selected list for every item (n items × m selected), a Set answers in one step. Clear the box to search everything again; the worst keystroke is the first one, when every item matches.

      The classes, to scale

      1101001,00010,000100,0001e61e71e81e91e101e111e121e131e141e151e161e171e181e191e201e211e221e231e241e251e261e271e281e291e301e311e321e331e341e35n = 32operations, at nO(1)O(log n)O(n)O(n log n)O(n²)O(n³)O(2ⁿ)O(n!)
      ClassOperations at n = 32At a billion a secondTypical of
      O(1)11 nsArray index, hash lookup, push to a stack
      O(log n)55 nsBinary search, balanced-tree lookup
      O(n)3232 nsA single loop, a linear scan, rendering a list
      O(n log n)160160 nsMerge sort, Array.prototype.sort, most good sorts
      O(n²)1,0241 µsNested loops, bubble sort, comparing every pair, naive layout of n items against n items
      O(n³)32,76833 µsTriple loops, naive matrix multiplication
      O(2ⁿ)4,294,967,2964.3 sEvery subset, naive recursive Fibonacci, brute-force search
      O(n!)2.63e+358.4e+18 yearsEvery ordering: the travelling salesman by brute force

      Hover a line or a row. Drag n up and watch which classes leave the chart.

      Notes

      The demo measures the real filter in the keystroke handler with performance.now(), on your machine, so the numbers are yours. Two budgets are drawn: 16.7 ms is one frame at 60 Hz, past which typing drops frames; 100 ms is the long-standing threshold for feeling instantaneous (Nielsen, Response Times: The 3 Important Limits, 1993). The quadratic line is the most common accidental one in interface code: array.includes, indexOf or find inside a loop over another array. The fix is a Set or a Map built once.

      Operations are the bare function of n with no constant factors, which is what Big O describes and also why it is not a benchmark: a fast O(n²) beats a slow O(n log n) for small n every day. A billion operations a second is a round figure for one core doing simple work; real code with cache misses and branches does far fewer. Sources: Cormen, Leiserson, Rivest and Stein, Introduction to Algorithms; the ECMAScript specification (Array.prototype.sort must be stable; engines use TimSort, O(n log n)).