Big-O, Visually

in reviewThis lesson is complete and being validated before release - details may still change.

Big-O, visually

Loading interactive demo…

The plot doubles with every gridline: n across, from 4 up to the chosen maximum, and steps up. Each routine runs over arrays of every size, every look at an element counts as one basic step, and the count becomes a point. The faint curves are the five shapes of growth; the strips beneath list the counts by size, the ratio between neighbouring sizes, and the orders.Take the tour, or press and explore. Legend:

The panel beside the stage is the real GrowthMeter class from the published library executing in your browser, with the current line highlighted.

The routine's measured points, labelled with their step counts.
The comparison routine's points, hollow, measured over the same sizes.
The dashed curve: the shape the routine's order predicts.
The other shapes, and the faint finished measurement.

n is the size under way and steps the count it produced; shape is the order's value at that n; on doubling is the count divided by the count at half the size; order is the name the routine earns once every size is in.

The code panel shows bare executable code by default. The bar above it names the file (hover the name for the full published path); options holds the toggles: comments, the tracer instrumentation that produces this visualization, and verbose names for the terse identifiers (display only: the default is the byte-exact published file). The view switch adds plain-English narration: both interleaves it with the code, pseudo shows only the pseudocode. hide code collapses the panel; the rail it leaves behind brings it back.

Keys: Space play/pause · ←/→ step · Home/End jump · R reset · F fullscreen · G guided tour

Count the steps, then forget the count. Every routine on the stage runs over an array and counts one basic step per look at an element. The counts themselves are not the point; the stage plots them only to show their shape. When the array doubles, a constant routine does the same work, a logarithmic one does one more step, a linear one does twice the work, a linearithmic one a little more than twice, and a quadratic one four times. That response to doubling is what Big-O names, and it is all the notation keeps.

The definition. A function $f$ is $O(g)$ when some constant $c$ and some size $n_0$ make

f(n) \le c \cdot g(n) \quad \text{for every } n \ge n_0 .

Past $n_0$ , $f$ never climbs above a fixed multiple of $g$ . The $c$ is why constants drop: $3n$ and $300n$ are both $O(n)$ , with $c = 3$ and $c = 300$ . The $n_0$ is why lower terms drop: $n^2 + 50n$ is $O(n^2)$ because once $n \ge 50$ the $50n$ is at most another $n^2$ , so $c = 2$ works from $n_0 = 50$ on. On the stage's doubling axes a constant factor shifts a series up or down by a fixed amount and a lower term bends it only at the small end; neither changes the slope the points settle into, and the slope is the order.

The five shapes, and the two in between. The orders you meet most, slowest-growing first:

order	doubling $n$ does	an example
$O(1)$	nothing	read an array slot, push onto a stack
$O(\log n)$	adds one step	binary search, a balanced tree lookup
$O(n)$	doubles the work	a scan, a sum, a linear search
$O(n \log n)$	a bit over doubles	merge sort, heapsort
$O(n^2)$	quadruples	every pair, insertion sort's worst case

Beyond these sit $O(2^n)$ , where adding one element doubles the work, and $O(n!)$ , where it multiplies the work by $n$ . The gap between neighbours in the table is what makes the choice of algorithm matter: at $n = 10^6$ , $n^2$ is a million times $n$ , and $\log_2 n$ is about $20$ .

Which count? A routine's steps can depend on more than $n$ : a linear search stops early when it finds the key. Analysis names the case: the worst case is the bound that always holds, the average case assumes a distribution of inputs, and the best case is rarely worth stating. Unqualified, $O(\cdot)$ means the worst case. The stage's routines take the same count on every array of a given size, so the question does not arise here; it will in the next lesson, and in every hash table lesson ever written.

The other letters. $O$ is an upper bound: $n$ is $O(n^2)$ , true and useless. $\Omega$ is the lower bound, and $\Theta$ says both at once: the counts on the stage are $\Theta$ of their shapes, not merely $O$ . In everyday use "the algorithm is $O(n \log n)$ " nearly always means $\Theta$ , a tight bound on the worst case, and this site follows that habit.

What comes next. The first algorithm in the arc with a logarithmic count: binary search halves a sorted array until one slot is left, which is exactly the stage's logarithmic routine with a key to look for. After it, every data structure in the arc is a way of buying a lower order for some operation: a heap for the minimum, a hash table for membership, disjoint sets for connection, a balanced tree for order.

Choices worth reading closely in the implementation (the code panel's comments and tracer checkboxes reveal the full published file):

One counter, one definition of a step. Every routine calls touch once per look at an element and nothing else counts. A cost model needs exactly this: a single named operation whose count is the measure, chosen so that everything else the routine does is proportional to it.
The shapes are integers. bound computes $\lceil \log_2 n \rceil$ by doubling a power of two until it reaches $n$ , never by a floating-point logarithm, so the value a Node build records is the value the browser recomputes. Only the plot's positions use a real logarithm, and nothing branches on them.
The routines are the pure cases. halve keeps half of what is left; splitAndMerge is a merge sort stripped to its touches; pairs visits every ordered pair. At a power of two each count equals its shape exactly, which is why the points sit on the dashed curve. Off a power of two they fall a little below it, which is what $f \le c \cdot g$ allows.
double carries the ratio, not just the counts. The library rounds the quotient to two decimals once, so the narration, the strip, and the metric all show the same number, and a learner comparing $2.67$ to $2.5$ to $2.4$ sees the linearithmic ratio creeping toward $2$ as $\log n$ grows ever more slowly.
classify emits a name the meter never computed. The order is looked up from the routine, not inferred from the points. That is honest: Big-O is a statement proved about an algorithm, and a finite table of measurements can only illustrate it.

The O came from number theory, not computing. Paul Bachmann introduced it in the second volume of his Analytische Zahlentheorie in 1894 to write how closely one function approximates another, the letter standing for Ordnung, the order of the approximation. Edmund Landau took it up in his 1909 treatise on the primes and added little o; the pair became the Landau symbols. Computing borrowed them in the 1960s and 1970s, once Hartmanis and Stearns had made an algorithm's running time a mathematical object and Donald Knuth had made counting its steps a discipline.

1894Paul Bachmann - Introduces the O symbol in the second volume of Analytische Zahlentheorie, for the order of an approximation.source
1909Edmund Landau - Adopts O and introduces o in his Handbuch der Lehre von der Verteilung der Primzahlen; the two become the Landau symbols.source
1965Juris Hartmanis and Richard Stearns - 'On the Computational Complexity of Algorithms' defines complexity classes by the time a Turing machine needs, founding computational complexity theory; the pair receive the 1993 Turing Award for it.source
1968Donald Knuth - Publishes the first volume of The Art of Computer Programming, which analyses the running time of its algorithms step by step and popularizes the asymptotic notation in computing.source
1976Donald Knuth - 'Big Omicron and Big Omega and Big Theta' in SIGACT News proposes the modern conventions: O for upper bounds, Omega for lower bounds, and Theta for both at once.source

Used today

Choosing a data structure - Every lesson that follows in this arc is a trade of one order for another: a lookup in O(log n) or O(1) instead of O(n), paid for with structure.
Reading documentation - A library that says its sort is O(n log n) or its lookup is amortized O(1) is telling you what happens when your data doubles.
Finding the bottleneck - A loop inside a loop over the same collection is O(n^2), and the first thing a profiler and a reviewer both look for.

Did you know

The O originally stood for Ordnung, the German word for order, as in the order of an approximation; Bachmann coined it for number theory, where it is still used alongside Vinogradov's alternative symbol.source
Writing f(n) = O(g(n)) with an equals sign is a well-known abuse of notation, since O(x) = O(x^2) is true but O(x^2) = O(x) is not. Knuth defended it as a one-way equality: Aristotle is a man, but a man is not necessarily Aristotle.source
Knuth's 1976 paper is titled Big Omicron and Big Omega and Big Theta, treating the O as a Greek capital omicron. The name Big Omicron appears nowhere else in the paper and almost nobody uses it.source
Knuth wrote the paper as a letter to SIGACT News because authors kept using O-notation for lower bounds, rejecting a sorting method for being O(n^2) when they meant it could not do better; he proposed Omega for that.source
In 1910 G. H. Hardy proposed his own symbols for the same relations in his tract Orders of Infinity, then used Landau's O and o himself in nearly all his later work. Only his symbol for the two-sided bound survives, in analytic number theory.source

routine

compare

max n

n: 64
steps: 64
shape: 64
on doubling: 2x
order: O(n)

growth-meter.ts

import type { Tracer } from "../trace";/** The five shapes of growth the meter can run, slowest-growing first. */export const GROWTH_ROUTINES = ["constant", "logarithmic", "linear", "linearithmic", "quadratic"] as const;export type GrowthRoutine = (typeof GROWTH_ROUTINES)[number];/** The order each routine belongs to, as the notation writes it. */export const GROWTH_ORDERS: Record<GrowthRoutine, string> = {  constant: "O(1)",  logarithmic: "O(log n)",  linear: "O(n)",  linearithmic: "O(n log n)",  quadratic: "O(n^2)",};/** The smallest and largest array the meter will run a routine over. */export const GROWTH_MIN_SIZE = 1;export const GROWTH_MAX_SIZE = 256;/** Sizes one measurement may run, so a trace stays short. */export const GROWTH_MAX_SIZES = 12;export interface GrowthSample {  n: number;  /** Basic steps the routine took on an array of n elements. */  steps: number;  basicSteps: number;  /** The shape's value at n: 1, ceil(log2 n), n, n ceil(log2 n), or n^2. */  bound: number;  shapeValue: number;}export interface GrowthReport {  routine: GrowthRoutine;  order: string;  samples: GrowthSample[];  /** steps(n_i) / steps(n_i-1) for each size after the first, to two decimals. */  ratios: number[];}/** * Counts the work five textbook routines do on arrays of growing size, * so the shape of the count can be read off: when the input doubles, * constant work stays the same, logarithmic work goes up by one step, * linear work doubles, linearithmic work a little more than doubles, * and quadratic work quadruples. Every routine touches array elements * and counts each touch as one basic step; the count is exact and * integer, so the same sizes give the same trace everywhere. Big-O * names the shape, not the count: the step counts here happen to sit * exactly on their shapes because the routines are the pure cases, * and a real program's constant factor and lower terms would only move * the points, never their response to doubling. * * Time: the routines themselves, O(1) to O(n^2) per size. Space: O(n). */export class GrowthMeter {  private steps = 0;  private basicSteps = 0;  constructor(private readonly tracer?: Tracer) {}  /** Runs the routine over an array of each size in turn, counting its steps and comparing neighbours. */  measure(routine: GrowthRoutine, sizes: readonly number[]): GrowthReport {    this.check(routine, sizes);    const samples: GrowthSample[] = [];    const ratios: number[] = [];    for (const n of sizes) {      // ▸ the next size: reset the step count and build an array of n values      this.tracer?.emit("run", { routine, n });      const values = Array.from({ length: n }, (_, i) => i);      this.steps = 0;      this.basicSteps = 0;      this.perform(routine, values);      const bound = GrowthMeter.bound(routine, n);      const shapeValue = GrowthMeter.shapeValue(routine, n);      const sample: GrowthSample = { n, steps: this.steps, bound };      const sample: GrowthSample = { n, basicSteps: this.basicSteps, shapeValue };      // ▸ the routine has run; record its steps beside the shape's value at n      this.tracer?.emit("count", { routine, n, steps: this.steps, bound });      this.tracer?.emit("count", { routine, n, basicSteps: this.basicSteps, shapeValue });      const previous = samples[samples.length - 1];      if (previous) {        const ratio = Math.round((100 * sample.steps) / Math.max(1, previous.steps)) / 100;        const doublingRatio = Math.round((100 * sample.basicSteps) / Math.max(1, previous.basicSteps)) / 100;        ratios.push(ratio);        ratios.push(doublingRatio);        // ▸ n doubled since the last size: how did the step count answer?        this.tracer?.emit("double", { routine, from: previous.n, to: n, before: previous.steps, after: sample.steps, ratio });        this.tracer?.emit("double", { routine, from: previous.n, to: n, before: previous.basicSteps, after: sample.basicSteps, doublingRatio });      }      samples.push(sample);    }    const order = GROWTH_ORDERS[routine];    // ▸ every size is in; the shape the counts follow is the routine's order    this.tracer?.emit("classify", { routine, order, sizes: sizes.length });    return { routine, order, samples, ratios };  }  /** The shape's value at n, in whole numbers: the bound a routine's count follows. */  static bound(routine: GrowthRoutine, n: number): number {  static shapeValue(routine: GrowthRoutine, n: number): number {    switch (routine) {      case "constant":        return 1;      case "logarithmic":        return GrowthMeter.ceilLog2(n);      case "linear":        return n;      case "linearithmic":        return n * GrowthMeter.ceilLog2(n);      case "quadratic":        return n * n;    }  }  /** The smallest k with 2^k >= n, by doubling, so no floating-point log is involved. */  static ceilLog2(n: number): number {    let k = 0;    let power = 1;    while (power < n) {      power *= 2;      k++;    }    return k;  }  private perform(routine: GrowthRoutine, values: readonly number[]): void {    switch (routine) {      case "constant":        this.first(values);        return;      case "logarithmic":        this.halve(values);        return;      case "linear":        this.scan(values);        return;      case "linearithmic":        this.splitAndMerge(values);        return;      case "quadratic":        this.pairs(values);        return;    }  }  /** One basic step: a look at an element. */  private touch(): void {    this.steps++;    this.basicSteps++;  }  /** Constant: read the first element, whatever the size. */  private first(values: readonly number[]): number | undefined {    this.touch();    return values[0];  }  /** Logarithmic: keep half of what is left until one element remains, one step per halving. */  private halve(values: readonly number[]): number {    let remaining = values.length;    while (remaining > 1) {      remaining = (remaining + 1) >> 1;      this.touch();    }    return remaining;  }  /** Linear: look at every element once. */  private scan(values: readonly number[]): number {    let total = 0;    for (const value of values) {      this.touch();      total += value;    }    return total;  }  /** Linearithmic: split in halves until single elements, then merge each level back, touching every element once per level. */  private splitAndMerge(values: readonly number[]): number[] {    if (values.length <= 1) return [...values];    const middle = values.length >> 1;    const left = this.splitAndMerge(values.slice(0, middle));    const right = this.splitAndMerge(values.slice(middle));    const merged: number[] = [];    let i = 0;    let j = 0;    while (i < left.length || j < right.length) {      this.touch();      if (j >= right.length || (i < left.length && left[i]! <= right[j]!)) merged.push(left[i++]!);      else merged.push(right[j++]!);    }    return merged;  }  /** Quadratic: look at every ordered pair of elements. */  private pairs(values: readonly number[]): number {    let matches = 0;    for (const a of values) {      for (const b of values) {        this.touch();        if (a === b) matches++;      }    }    return matches;  }  private check(routine: GrowthRoutine, sizes: readonly number[]): void {    if (!GROWTH_ROUTINES.includes(routine)) throw new RangeError(`unknown routine "${String(routine)}"`);    if (sizes.length === 0 || sizes.length > GROWTH_MAX_SIZES) throw new RangeError(`sizes must number 1 to ${GROWTH_MAX_SIZES}`);    sizes.forEach((n, index) => {      if (!Number.isInteger(n) || n < GROWTH_MIN_SIZE || n > GROWTH_MAX_SIZE) throw new RangeError(`size ${n} must be a whole number in [${GROWTH_MIN_SIZE}, ${GROWTH_MAX_SIZE}]`);      if (index > 0 && n <= sizes[index - 1]!) throw new RangeError("sizes must increase");    });  }}

routine =: quadratic
steps =: 4096
ratio =: 4
order =: O(n^2)
compare =: linear
compareSteps =: 64
compareRatio =: 2

Done: the quadratic routine is O(n^2), four times the work each time n doubles. At n = 64 it took 4096 steps, 4 times the size before, while the linear routine took 64, 2 times its size before.

order

doubling

n

does

an example

O(1)

nothing

read an array slot, push onto a stack

O(\log n)

adds one step

binary search, a balanced tree lookup

O(n)

doubles the work

a scan, a sum, a linear search

O(n \log n)

a bit over doubles

merge sort, heapsort

O(n^2)

quadruples

every pair, insertion sort's worst case

import type { Tracer } from "../trace";/** The five shapes of growth the meter can run, slowest-growing first. */export const GROWTH_ROUTINES = ["constant", "logarithmic", "linear", "linearithmic", "quadratic"] as const;export type GrowthRoutine = (typeof GROWTH_ROUTINES)[number];/** The order each routine belongs to, as the notation writes it. */export const GROWTH_ORDERS: Record<GrowthRoutine, string> = { constant: "O(1)", logarithmic: "O(log n)", linear: "O(n)", linearithmic: "O(n log n)", quadratic: "O(n^2)",};/** The smallest and largest array the meter will run a routine over. */export const GROWTH_MIN_SIZE = 1;export const GROWTH_MAX_SIZE = 256;/** Sizes one measurement may run, so a trace stays short. */export const GROWTH_MAX_SIZES = 12;export interface GrowthSample { n: number; /** Basic steps the routine took on an array of n elements. */ steps: number; basicSteps: number; /** The shape's value at n: 1, ceil(log2 n), n, n ceil(log2 n), or n^2. */ bound: number; shapeValue: number;}export interface GrowthReport { routine: GrowthRoutine; order: string; samples: GrowthSample[]; /** steps(n_i) / steps(n_i-1) for each size after the first, to two decimals. */ ratios: number[];}/** * Counts the work five textbook routines do on arrays of growing size, * so the shape of the count can be read off: when the input doubles, * constant work stays the same, logarithmic work goes up by one step, * linear work doubles, linearithmic work a little more than doubles, * and quadratic work quadruples. Every routine touches array elements * and counts each touch as one basic step; the count is exact and * integer, so the same sizes give the same trace everywhere. Big-O * names the shape, not the count: the step counts here happen to sit * exactly on their shapes because the routines are the pure cases, * and a real program's constant factor and lower terms would only move * the points, never their response to doubling. * * Time: the routines themselves, O(1) to O(n^2) per size. Space: O(n). */export class GrowthMeter { private steps = 0; private basicSteps = 0; constructor(private readonly tracer?: Tracer) {} /** Runs the routine over an array of each size in turn, counting its steps and comparing neighbours. */ measure(routine: GrowthRoutine, sizes: readonly number[]): GrowthReport { this.check(routine, sizes); const samples: GrowthSample[] = []; const ratios: number[] = []; for (const n of sizes) { // ▸ the next size: reset the step count and build an array of n values this.tracer?.emit("run", { routine, n }); const values = Array.from({ length: n }, (_, i) => i); this.steps = 0; this.basicSteps = 0; this.perform(routine, values); const bound = GrowthMeter.bound(routine, n); const shapeValue = GrowthMeter.shapeValue(routine, n); const sample: GrowthSample = { n, steps: this.steps, bound }; const sample: GrowthSample = { n, basicSteps: this.basicSteps, shapeValue }; // ▸ the routine has run; record its steps beside the shape's value at n this.tracer?.emit("count", { routine, n, steps: this.steps, bound }); this.tracer?.emit("count", { routine, n, basicSteps: this.basicSteps, shapeValue }); const previous = samples[samples.length - 1]; if (previous) { const ratio = Math.round((100 * sample.steps) / Math.max(1, previous.steps)) / 100; const doublingRatio = Math.round((100 * sample.basicSteps) / Math.max(1, previous.basicSteps)) / 100; ratios.push(ratio); ratios.push(doublingRatio); // ▸ n doubled since the last size: how did the step count answer? this.tracer?.emit("double", { routine, from: previous.n, to: n, before: previous.steps, after: sample.steps, ratio }); this.tracer?.emit("double", { routine, from: previous.n, to: n, before: previous.basicSteps, after: sample.basicSteps, doublingRatio }); } samples.push(sample); } const order = GROWTH_ORDERS[routine]; // ▸ every size is in; the shape the counts follow is the routine's order this.tracer?.emit("classify", { routine, order, sizes: sizes.length }); return { routine, order, samples, ratios }; } /** The shape's value at n, in whole numbers: the bound a routine's count follows. */ static bound(routine: GrowthRoutine, n: number): number { static shapeValue(routine: GrowthRoutine, n: number): number { switch (routine) { case "constant": return 1; case "logarithmic": return GrowthMeter.ceilLog2(n); case "linear": return n; case "linearithmic": return n * GrowthMeter.ceilLog2(n); case "quadratic": return n * n; } } /** The smallest k with 2^k >= n, by doubling, so no floating-point log is involved. */ static ceilLog2(n: number): number { let k = 0; let power = 1; while (power < n) { power *= 2; k++; } return k; } private perform(routine: GrowthRoutine, values: readonly number[]): void { switch (routine) { case "constant": this.first(values); return; case "logarithmic": this.halve(values); return; case "linear": this.scan(values); return; case "linearithmic": this.splitAndMerge(values); return; case "quadratic": this.pairs(values); return; } } /** One basic step: a look at an element. */ private touch(): void { this.steps++; this.basicSteps++; } /** Constant: read the first element, whatever the size. */ private first(values: readonly number[]): number | undefined { this.touch(); return values[0]; } /** Logarithmic: keep half of what is left until one element remains, one step per halving. */ private halve(values: readonly number[]): number { let remaining = values.length; while (remaining > 1) { remaining = (remaining + 1) >> 1; this.touch(); } return remaining; } /** Linear: look at every element once. */ private scan(values: readonly number[]): number { let total = 0; for (const value of values) { this.touch(); total += value; } return total; } /** Linearithmic: split in halves until single elements, then merge each level back, touching every element once per level. */ private splitAndMerge(values: readonly number[]): number[] { if (values.length <= 1) return [...values]; const middle = values.length >> 1; const left = this.splitAndMerge(values.slice(0, middle)); const right = this.splitAndMerge(values.slice(middle)); const merged: number[] = []; let i = 0; let j = 0; while (i < left.length || j < right.length) { this.touch(); if (j >= right.length || (i < left.length && left[i]! <= right[j]!)) merged.push(left[i++]!); else merged.push(right[j++]!); } return merged; } /** Quadratic: look at every ordered pair of elements. */ private pairs(values: readonly number[]): number { let matches = 0; for (const a of values) { for (const b of values) { this.touch(); if (a === b) matches++; } } return matches; } private check(routine: GrowthRoutine, sizes: readonly number[]): void { if (!GROWTH_ROUTINES.includes(routine)) throw new RangeError(`unknown routine "${String(routine)}"`); if (sizes.length === 0 || sizes.length > GROWTH_MAX_SIZES) throw new RangeError(`sizes must number 1 to ${GROWTH_MAX_SIZES}`); sizes.forEach((n, index) => { if (!Number.isInteger(n) || n < GROWTH_MIN_SIZE || n > GROWTH_MAX_SIZE) throw new RangeError(`size ${n} must be a whole number in [${GROWTH_MIN_SIZE}, ${GROWTH_MAX_SIZE}]`); if (index > 0 && n <= sizes[index - 1]!) throw new RangeError("sizes must increase"); }); }}