Big-O Complexity Explorer

See how algorithm complexity classes grow as input size N increases.

Worked example — Big-O Complexity Explorer

O(1)	1
O(log N)	7
O(N)	100
O(N log N)	664
O(N²)	10,000

These are the values the calculator shows when the page opens. Change any input above to recompute them.

Loading interactive simulation...

Lesson

The theory — Big-O Complexity Explorer

Big-O is an upper bound on growth, not a measurement of time. Saying an algorithm is O(N²) claims that beyond some input size its work stays below a fixed multiple of N² — it says nothing about seconds, and nothing at all about small inputs.

What each symbol means

N: the input size — how many items the algorithm is handed. It is the number set above, anywhere from 2 to 1,000,000.
f(N): the work actually done at that size, counted in abstract operations rather than seconds.
c: a constant multiplier the notation is allowed to hide. The claim is f(N) ≤ c·g(N); c might be 2 or 2000, and that is precisely the information Big-O discards.
n₀: the size beyond which the bound has to hold. Below n₀ the classes may sit in any order whatsoever, which is why the five numbers above bunch together at small N.

Where the formula comes from

Start from the claim that needs making precise: the work f(N) eventually grows no faster than some reference function g(N).
“No faster” has to tolerate a constant factor, because tightening an inner loop changes the constant and not the shape. So allow a multiplier: f(N) ≤ c·g(N).
And “eventually” has to excuse small inputs, where anything can happen. Require the inequality only once N ≥ n₀. Together: f(N) = O(g(N)) means there exist some c > 0 and some n₀ with f(N) ≤ c·g(N) for every N ≥ n₀.

How to read what you see

The five rows are one input size run through five growth classes with every constant set to 1 — so they are operation counts, not runtimes. At the default N = 100 they read 1, 7, 100, 664 and 10,000. The logarithm is base 2: log₂ 100 ≈ 6.64, which is why O(log N) shows 7 and O(N log N) shows 664 rather than 700.

Assumes: That one operation costs the same as any other, and that the count is exact rather than measured. That is what makes the comparison clean, and equally what makes it abstract — memory access patterns, cache behaviour and disk all sit outside this model, and on real hardware they routinely decide which of two algorithms wins.
Breaks when: The bound promises nothing below n₀, and you can watch that directly: set N = 2 and the five classes read 1, 1, 2, 2 and 4 — all but indistinguishable. The ordering the notation guarantees only emerges once N is large, which is how an O(N²) method with a small constant can beat an O(N log N) one on every input you will ever actually have.

When growth outruns tuning 🖖

Big-O describes how work grows as input size increases. A single loop grows roughly with N, nested loops often grow with N², and branching recursion can grow exponentially. The important lesson is scale: at small N many approaches look similar, but at larger N the growth class dominates runtime.

Reading the doubling test 🖖

The clearest way to feel a growth class is to double the input and watch the work. Under O(log N) the effort barely moves — binary search finds one item among a million in about 20 comparisons. Under O(N) the work doubles, and under O(N²) it quadruples. Slide N in this tool and watch the gaps widen from invisible to overwhelming.

When a faster class loses 🖖

A lower growth class does not guarantee a faster program. Computer scientists call the exceptions galactic algorithms: methods with a superior Big-O whose hidden constant factor is so enormous they only overtake simpler methods on inputs bigger than anything in the physical universe. Several record-holding matrix-multiplication algorithms are never run in practice for exactly this reason — Big-O quietly drops the constants that decide real-world speed.

Problem solved in full

Where the chasm opens between N log N and N ² 5 steps
At N = 100 the panel shows 664 for N log N and 10 000 for N². That is only a factor of fifteen — hardly the chasm complexity classes are supposed to be. Work out where the chasm actually opens.
1. Start with the two numbers. log₂ 100 is 6.6439, so N log₂ N is 664 and N² is 10 000.
  
  $N lo g_{2} N = 100 \times 6.6439 = 664, N^{2} = 10000$
2. The ratio between them is not a constant, which is what puts them in different complexity classes. Divide and the N cancels once, leaving N/log N — a quantity that grows without bound, just slowly.
3. At N = 100 it is 15.1. That is real but unimpressive: a fifteen-fold speed-up is the kind of thing a better constant factor could hand you, which is exactly why benchmarks on small inputs mislead.
  
  $\frac{N ^{2}}{N lo g _{2} N} = \frac{N}{lo g _{2} N} = \frac{100}{6.6439} = 15.1$
4. Now put in a million. The logarithm has barely moved — from 6.6 to 19.9, a factor of three — while N has grown ten thousand-fold. The ratio is now 50 172.
  
  $N = 1 0^{6} : \frac{N}{lo g _{2} N} = \frac{1 0 ^{6}}{19.93} = 50172$
5. And it never turns around. The derivative of N/log N is positive for every N above e, so no input size exists beyond which the quadratic algorithm catches up.
  
  $\frac{d}{d N} (\frac{N}{lo g _{2} N}) > 0 for N > e ⟹ the gap only widens$
Answer

The tool prints 664 against 10 000 at N = 100. The number worth carrying is the other one: at a million the same two curves are 50 172 apart. Complexity classes are not claims about a hundred items, and comparing them there is the standard way to talk yourself into the wrong algorithm — a fifteen-fold gap looks like something a faster language could close. Push the slider up and watch the ratio go with it. That is also why the logarithm is so often ignored in practice: it grew by a factor of three while the input grew by ten thousand.

$\frac{N ^{2}}{N lo g N} = \frac{N}{lo g N} : 15 \times at 100, 50172 \times at 1 0^{6}$

Learning path

Counting work, not seconds

Leads to sorting-race

References (1)

The definition the lesson states, and the case for using it carefully: D. E. Knuth, “Big Omicron and big Omega and big Theta.” ACM SIGACT News 8, 18–24, 1976.

By the 42Math team · Updated 2026-06-10

Reviewed against published sources. Corrections welcome. Editorial policy · Corrections

All Computing lessons →

Example problems

Small N=20 - All curves at N=20
N=1000 - N=1000: polynomial curves diverge
Log scale - Log scale reveals growth differences
Hidden constants - With c=50, 50N log N and N² meet near N=439