Big-O explorer and benchmark

⛶ Full screen (or F) gives the open tab’s picture the whole screen — the growth curves, the benchmark fit, the sorting bars, the Fibonacci call tree or the attention chart — using the browser’s full screen where it is allowed, otherwise a full-window layer (iPhone). The picture is redrawn as tall as the screen allows, with its controls above it; Escape leaves.

Growth curves plots O(1), O(log n), O(√n), O(n), O(n log n), O(n²), O(n³), O(2ⁿ), and O(n!) together, plus two adjustable curves for a growth race: nᵏ (slide k from 1 to 10) and bⁿ (type b, from 1.001 to 3). Tick the classes to compare and pick how far n goes. Switch between linear, log-y (an exponential becomes a straight line) and log-log axes (every power nᵏ becomes a straight line of slope k). With both race curves shown, the tool says where bⁿ overtakes nᵏ for good — for 1.01ⁿ against n³ that is n = 2,339 — comparing n ln b with k ln n so nothing overflows.

Time & budget turns the classes into wall-clock time. Set a speed in simple operations per second (about 10^8 for a JavaScript or C loop, 10^6 for interpreted Python) and a budget; the table gives the largest n each class can handle, and how long each takes at the sizes you list. At 10^9 operations per second, one second is enough for n = 10^9 linear steps, n ≈ 31,600 for quadratic, n = 29 for 2ⁿ, and n = 12 for n!. Factorials and powers are computed with logarithms, so even 1000! has a time (in multiples of the age of the universe). The budget buttons run from 1 ms to 1 year.

Benchmark & fit times real code. Write setup(n) to build the input — it is not timed — and run(input, n), which is. The tool runs in a background worker, for each size repeating run until a batch takes at least 20 ms, and keeps the median of five batches. It then fits time ≈ a + c·g(n) for every class, weighting each point by its relative error, and reports:

Examples cover summing an array, the built-in sort, all-pairs loops, binary search, Map lookups, naive Fibonacci, bubble sort, and matrix multiplication. To get clean results, use a range of n that spans at least two orders of magnitude, and make the work grow with n: a benchmark whose run takes a few nanoseconds is dominated by loop overhead and the JIT. If run changes its input (sorting in place, say), copy it first — every repetition reuses the same input. Stop ends a run early; any size that takes over 20 s stops the run automatically.

Cheat sheet is a colour-coded reference in the style of the well-known Big-O cheat sheet: the complexity chart (operations against elements, from excellent to horrible), then average and worst-case costs of operations on arrays, stacks, queues, linked lists, skip lists, hash tables, BSTs, Cartesian trees, B-trees, red-black, splay, and AVL trees, k-d trees, and tries; heap operations (binary, binomial, Fibonacci, pairing, Brodal); array sorting algorithms (best, average, worst, space, stability); graph algorithms; and other common algorithms. Θ marks the typical bound, O the worst case, Ω the best case. Values follow CLRS and Sedgewick & Wayne. Colours are relative to the problem: O(n log n) is fair for a sort but bad for a single lookup. Type in the search box to filter every table at once.

Sort visualiser animates eleven sorts — bubble, insertion, selection, Shell, quicksort with a naive or median-of-three pivot, mergesort, heapsort, a simplified Timsort, counting, and LSD radix — on random, nearly sorted, reversed, or few-unique data, with play, pause, single-step, speed, and size controls. Comparisons flash yellow, swaps red, and writes orange; the counters show how the totals compare with n log₂ n and n². Try quicksort with the naive pivot on reversed data to see its O(n²) worst case, then switch to median-of-three. ▶ Visualise in the cheat sheet jumps straight to an algorithm.

Fibonacci calls draws the call tree of the naive recursive fib(n) for n from 0 to 12, one node per call, coloured by its argument, so repeated colours are repeated work (fib(5) computes fib(2) three times and fib(3) twice). Tick Memoise and the tree collapses into a single path with short side-branches: a call whose answer is already cached is a small grey leaf that does no work. Animate calls and Step show the calls in the order they happen (depth first). The readout puts the call count beside 2F(n+1) − 1 (naive) and n + 1 (distinct values), and a table carries the race on to n = 40: 242,785 naive calls for n = 25 against 26 computations.

Recursion trees unrolls a divide-and-conquer recurrence level by level, with T(1) = 0: merge sort T(n) = 2T(n/2) + n, binary search T(n) = T(n/2) + 1, and visiting every node of a balanced tree T(n) = 2T(n/2) + 1. Each row is one level, its sub-problems drawn with width proportional to size, and the work done on that level at the right. Merge sort does n work on each of log₂ n levels, so T(n) = n log₂ n exactly when n is a power of 2 (T(16) = 64, T(1024) = 10,240). Other n split into ⌈n/2⌉ and ⌊n/2⌋; very large n (up to 10⁹) are drawn as "pieces × size" per level.

Halving is binary search on a sorted array of n items, n from 1 to 10¹² (type it, 1e9 works, or use the slider). The top strip is the whole array with the target in red; each row below is the range before one comparison, split at its middle, with the kept half coloured. Search animates it; Step goes one comparison at a time. Beside it are the comparisons used, log₂ n, ⌈log₂ n⌉, the bits needed for n (⌊log₂ n⌋ + 1, computed exactly, not with floating-point logs), and the height ⌊log₂ n⌋ of a balanced tree holding n keys: all "how many times can you halve n?", give or take one. Below: the in-your-head estimate (write n ≈ m × 1000ʲ, then log₂ n ≈ 10j + log₂ m, so 64 million ≈ 26) and the height log_B n of a B-tree with branching factor B.

Amortised append appends n items to a dynamic array that starts with a given capacity and, when full, either grows by a factor g (×2 like Java’s ArrayList, ×1.5 like many C++ libraries, ×1.125 like CPython; the new capacity is ⌈g × capacity⌉, at least one more) or by a constant number of slots. Every element written counts, copies included. The bars are the cost of each append, with the spikes at resizes and the running average; the accounting view charges each append a fixed number of tokens (3 for doubling, 1 + g/(g − 1) in general, 3 for a constant increment) and plots what is left in the bank. With geometric growth it never goes negative; with a constant increment it soon does, because the copying is quadratic. The table repeats the book’s run for n = 10, 1,000 and 1,000,000 under the current rule (25, 2,023 and 2,048,575 writes with doubling). Up to 10⁷ appends are counted; the charts show the first 2,000.

Attention & KV cache is the same arithmetic applied to language models. Attention vs SSM plots the work per layer over a context of N tokens: self-attention scores every pair of tokens (N²), a state-space model such as Mamba updates a fixed-size state once per token (N); the table shows what doubling the context does (×4 against ×2). KV cache: cumulative work counts the work of generating N tokens one at a time, where step i sees i tokens. Without a cache every step recomputes the keys and values of all earlier tokens: 1 + 2 + … + N = N(N+1)/2 projections, O(N²), and recomputing the whole causal attention each step adds up to N(N+1)(N+2)/6, O(N³). With a cache each step projects one new token, N in all, O(N), but still scores its query against every cached key, so attention stays Σ i = O(N²) — the cache removes the recomputation, not attention’s quadratic cost. Both charts are log-log.

Revision is for interview preparation, in five parts (pick one at the top):