How does an algorithm's cost grow as the input grows? Race the six complexity classes against each other and watch the ones that look fine at n=10 become impossible at n=1000.
Overview
Quick Context
Big-O describes the growth rate of an algorithm's cost as input size n increases. It deliberately throws away constants and lower-order terms — an algorithm that takes 3n + 50 steps is simply O(n), because for large n the 3 and the 50 stop mattering.
Controls
input size n20
Show curves
Growth Curves
step 0
Insight
Big-O describes how work grows with input size — it ignores constants and small terms, because at scale only the shape of growth matters.
Where VizLearn's algorithms land
O(log n) — binary search
O(n) — linear search, counting sort
O(n log n) — merge sort, quick sort
O(n²) — bubble, insertion, selection
O(2ⁿ) — naive recursive Fibonacci
Big-O Notation and Time Complexity
The language for saying how an algorithm behaves when the data gets big.
Why Ignore the Constants?
Because hardware changes and growth does not. A machine twice as fast halves every constant, but an O(n²) algorithm is still O(n²) — double the input and you quadruple the work, forever.
Slide n and watch the table. At n = 10 every row looks affordable. By n = 1000 the quadratic column is a million operations and the exponential column has left the universe behind.
The Six Classes You Will Meet
O(1) constant — cost never changes. Array index lookup, hash table access, stack push.
O(log n) logarithmic — each step halves the problem. Binary search, balanced tree operations. Doubling n adds just one step.
O(n) linear — touch every item once. Linear search, summing an array.
O(n log n) — the practical floor for comparison sorting. Merge sort, quick sort, heap sort.
O(n²) quadratic — nested loops over the data. Bubble, insertion and selection sort. Fine for 100 items, painful for 100,000.
O(2ⁿ) exponential — every extra element doubles the work. Naive recursive Fibonacci, brute-force subsets. Intractable beyond roughly n = 40.
Best, average and worst case
Big O usually refers to the worst case, and the other two matter in practice.
Algorithm
Best
Average
Worst
Quick sort
O(n log n)
O(n log n)
O(n²)
Merge sort
O(n log n)
O(n log n)
O(n log n)
Insertion sort
O(n)
O(n²)
O(n²)
Hash table lookup
O(1)
O(1)
O(n)
Two rows deserve comment.
Quick sort is O(n²) in the worst case and is the practical default anyway, because the worst case requires a pathological pivot sequence and randomised pivots make it vanishingly unlikely. Merge sort's guarantee is stronger and its constants are worse.
Insertion sort is O(n) on already-sorted input, which is why real sorting implementations use it for small or nearly-sorted subarrays inside a larger algorithm.
The related idea is amortised complexity: appending to a Python list is O(1) amortised, because occasional reallocations are spread across many cheap appends. Any individual append may be O(n); the average over a sequence is constant.
Space Complexity Counts Too
The same notation describes memory. Merge sort is O(n log n) time but needs O(n) extra space for its temporary arrays; quick sort sorts in place with only O(log n) stack space. When memory is the constraint, that difference decides which one you use.
Counting growth, not seconds
Big O describes how the work an algorithm does grows as the input grows. It deliberately ignores constants and hardware, because those change and the growth rate does not.
An algorithm that takes 3n + 50 steps is O(n). One that takes n²/2 steps is O(n²). The constants are dropped, because for large enough n the shape of the curve is what decides whether the program finishes.
Complexity
Name
n = 10
n = 1,000
n = 1,000,000
O(1)
Constant
1
1
1
O(log n)
Logarithmic
3
10
20
O(n)
Linear
10
1,000
1,000,000
O(n log n)
Linearithmic
30
10,000
20,000,000
O(n²)
Quadratic
100
1,000,000
10¹²
O(2ⁿ)
Exponential
1,024
astronomical
impossible
That table is the whole argument. At n = 1,000,000, an O(n log n) algorithm does 20 million operations — a fraction of a second. An O(n²) algorithm does 10¹² — hours. The difference is not an optimisation; it is the difference between working and not.
Reading complexity from code
The rules are mechanical once you see them.
A loop over the input is O(n).
Nested loops multiply. Two loops over n is O(n²); three is O(n³).
Sequential loops add, and the larger term wins: O(n) + O(n²) = O(n²).
Halving the search space each step is O(log n). Binary search on a million items takes 20 steps, because 2²⁰ ≈ 1,000,000.
Dictionary and set lookups are O(1). This is the single most useful fact for writing fast Python.
# O(n^2) - for each item, scan the whole list
for a in items:
if a in other_list: # this scan is O(n)
...
# O(n) - build a set once, then constant-time lookups
other = set(other_list)
for a in items:
if a in other: # O(1)
...
That transformation — replacing a repeated scan with a pre-built set or dictionary — is the most common and most effective optimisation in everyday code, and it usually makes the code shorter as well.
Counting the operations, and watching the ratios
Big-O is a claim about how work grows when the input grows. That claim is testable: count the actual operations at several sizes and look at what happens to the count when n doubles. Each class has its own signature, and you can read it straight off the numbers.
example_01.pyPython
def constant(n):
a = list(range(n))
return 1 if a else 0 # O(1): one look, whatever n is
def linear(n):
ops = 0
for _ in range(n):
ops += 1 # O(n)
return ops
def logarithmic(n):
ops, k = 0, n
while k > 1:
k //= 2
ops += 1 # O(log n)
return ops
def linearithmic(n):
ops, k = 0, n
while k > 1:
ops += n # n work, log n times
k //= 2
return ops
def quadratic(n):
ops = 0
for _ in range(n):
for _ in range(n):
ops += 1 # O(n^2)
return ops
sizes = [100, 200, 400, 800]
funcs = [("O(1)", constant), ("O(log n)", logarithmic), ("O(n)", linear),
("O(n log n)", linearithmic), ("O(n^2)", quadratic)]
print("%-11s %8s %8s %8s %8s ratio when n doubles" % tuple(
["class"] + [str(s) for s in sizes]))
for name, f in funcs:
counts = [f(s) for s in sizes]
ratios = [counts[i + 1] / counts[i] for i in range(len(counts) - 1)]
print("%-11s %8d %8d %8d %8d %s" % (
name, counts[0], counts[1], counts[2], counts[3],
", ".join("%.2f" % r for r in ratios)))
# Read the last column. That ratio IS the complexity class:
# O(1) stays 1.00 -- doubling n changes nothing
# O(log n) adds a constant -- ratio drifts toward 1
# O(n) exactly 2.00
# O(n log n) slightly above 2
# O(n^2) exactly 4.00
#
# Now the part the notation deliberately hides. Constants are dropped
# because they stop mattering -- but only eventually.
def fast_but_heavy(n):
return 1000 * n # O(n) with a big constant
def slow_but_light(n):
return n * n // 100 # O(n^2) with a small one
print()
print("%8s %14s %14s %s" % ("n", "1000n", "n^2/100", "which wins"))
for n in (10, 100, 1000, 10000, 100000, 1000000):
a, b = fast_but_heavy(n), slow_but_light(n)
verdict = "tie" if a == b else ("O(n)" if a < b else "O(n^2)")
print("%8d %14d %14d %s" % (n, a, b, verdict))
# The quadratic function is genuinely faster up to n = 100,000, where the
# two are exactly equal, and only past that does the linear one win. Big-O
# is a statement about the limit, not about your data -- which is why
# "asymptotically better" and "faster on this input" are different claims,
# and why real sorting libraries switch to insertion sort on small arrays.
Output
Things to try
Start at n = 10. Every curve is bunched together — at small inputs, complexity genuinely does not matter and the constants dominate.
Slide to n = 60. The exponential curve leaves the chart almost immediately, then the quadratic. The separation is the entire point of the notation.
Read the table at n = 1,000,000. O(log n) needs about 20 operations; O(n²) needs 10¹². That is the difference between instant and never.
Tick log-scale y. Each class becomes a straight line with its own slope — the cleanest way to see that these are genuinely different families, not just different constants.
Compare O(n) with O(n log n). The gap is small even at large n, which is why an O(n log n) sort is considered essentially as good as linear in practice.
Worth remembering
Big-O measures how cost grows, not how long something takes. Constants are ignored because growth is what survives faster hardware. Know roughly where each of your algorithms sits, and you can predict which one falls over first when the data gets big.
Space complexity
The same notation applies to memory, and it is frequently the binding constraint.
Approach
Time
Space
Sort in place
O(n log n)
O(1) extra
Merge sort
O(n log n)
O(n) extra
Recursion depth d
—
O(d) stack
Memoised recursion
Faster
O(states) extra
Recursion's space cost is easy to overlook: each call holds a frame on the stack, so recursion depth n uses O(n) memory and can overflow. Python's default limit is around 1,000 frames, which is why deep recursion needs converting to iteration or an explicit stack.
Memoisation is the classic time-for-space trade: recursive Fibonacci is O(2ⁿ) time and O(n) space; memoised it is O(n) time and O(n) space. That single change turns an impossible computation into an instant one.
Where it misleads
Big O is an asymptotic statement, and three caveats matter in real code.
Constants can dominate at realistic sizes. An O(n log n) algorithm with a huge constant can lose to an O(n²) one for n = 50. This is why real sorting implementations switch to insertion sort below a threshold.
Cache behaviour is invisible to the notation. Sequential array access can be several times faster than pointer-chasing through a linked list with the same complexity, because of memory locality.
The input's shape matters. Nearly-sorted data, many duplicates, or adversarial patterns can move an algorithm between its best and worst case.
So the discipline is: use Big O to rule out approaches that cannot possibly scale, and measure to choose between approaches that could. It is a filter, not a benchmark.
Questions people ask
Why drop constants? Because they depend on hardware and implementation, while the growth rate is a property of the algorithm. 2n and 100n are both O(n).
What is the difference between O, Θ and Ω? O is an upper bound, Ω a lower bound, Θ both. In practice people say O and mean Θ.
Is O(log n) fast? Extremely. Twenty steps for a million items, thirty for a billion. Any O(log n) algorithm is effectively instant at realistic sizes.
Which base for the logarithm? It does not matter — changing base multiplies by a constant, which is dropped. Base 2 is conventional because halving is the common operation.
Is O(n log n) much worse than O(n)? Only by the log factor — 20× at a million items. Both are practical; O(n²) is where the wall is.
Does Big O tell me which is faster? Only asymptotically. For a specific input size, measure.
Recap in one screen
Big O describes how work grows with input size, ignoring constants and hardware.
Loops over the input are O(n); nested loops multiply; halving is O(log n); dictionary lookups are O(1).
Replacing a repeated scan with a set or dictionary is the most common real-world speed-up.
Worst case is what Big O usually means; best and amortised cases explain why quick sort and list append are used anyway.
Use it to rule out what cannot scale, then measure to choose between what can.
Run it in Python
Five complexity classes, each with its operations counted rather than argued about, at three input sizes. The last block shows an O(n²) algorithm beating an O(n log n) one, which is the part the notation deliberately hides.
big_o.pyPython 3
# Big-O, counted. Every function below returns how much work it did.
import time
def constant(a): # O(1)
ops = 1
return a[len(a) // 2], ops
def logarithmic(a, target): # O(log n)
lo, hi, ops = 0, len(a) - 1, 0
while lo <= hi:
ops += 1
mid = (lo + hi) // 2
if a[mid] == target:
break
if a[mid] < target:
lo = mid + 1
else:
hi = mid - 1
return ops
def linear(a): # O(n)
ops = 0
for _ in a:
ops += 1
return ops
def linearithmic(a): # O(n log n) - merge sort's shape
if len(a) <= 1:
return 0
mid = len(a) // 2
return len(a) + linearithmic(a[:mid]) + linearithmic(a[mid:])
def quadratic(a): # O(n^2)
ops = 0
for _ in a:
for _ in a:
ops += 1
return ops
print(f"{'n':>7} {'O(1)':>6} {'O(log n)':>9} {'O(n)':>8} "
f"{'O(n log n)':>11} {'O(n^2)':>10}")
for n in (10, 100, 1000):
a = list(range(n))
print(f"{n:>7} {constant(a)[1]:>6} {logarithmic(a, n - 1):>9} "
f"{linear(a):>8} {linearithmic(a):>11} {quadratic(a):>10}")
print()
print("n grew 100x. O(log n) grew by 7. O(n^2) grew by 10,000.")
# --- constants, which big-O throws away --------------------------------
print()
def insertion(a): # O(n^2), tiny constant
a = a[:]
for i in range(1, len(a)):
key, j = a[i], i - 1
while j >= 0 and a[j] > key:
a[j + 1] = a[j]
j -= 1
a[j + 1] = key
return a
def merge(a): # O(n log n), heavier constant
if len(a) <= 1:
return a
mid = len(a) // 2
left, right = merge(a[:mid]), merge(a[mid:])
out, i, j = [], 0, 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
out.append(left[i]); i += 1
else:
out.append(right[j]); j += 1
return out + left[i:] + right[j:]
for n in (8, 16, 1000):
sample = [(i * 7919) % n for i in range(n)]
# A single small sort finishes faster than the clock can measure, so
# repeat it enough times to land on something the timer can see.
repeats = max(1, 100_000 // (n * n))
times = {}
for name, fn in (("insertion", insertion), ("merge", merge)):
start = time.time()
for _ in range(repeats):
fn(sample)
times[name] = (time.time() - start) / repeats
winner = min(times, key=times.get)
print(f"n={n:>5} (averaged over {repeats:>4}): "
f"insertion {times['insertion']*1000:>8.4f} ms, "
f"merge {times['merge']*1000:>8.4f} ms -> {winner} wins")
Output
How the code works
return a[len(a) // 2], opsIndexing is O(1) because the address is computed, not searched for. The size of the list never enters into it — that is the whole meaning of constant time.
mid = (lo + hi) // 2Halving the range each step means the op count rises by 1 when n doubles. In the table, n going from 10 to 1000 costs about seven more operations in total.
for _ in a: for _ in a:Nested loops over the same collection: n² operations. At n = 1000 that is a million, and it is the single most common accidental complexity in real code.
return len(a) + linearithmic(...) + ...Merge sort's recurrence made literal: linear work at each level, and log n levels. The number this returns is n log n up to a constant.
insertion beats merge at n = 16Big-O describes growth as n gets large and deliberately discards the constant factor. At small n that constant is everything — which is why CPython's sort switches to insertion sort for short runs.
Change one thing
Add an O(2ⁿ) row using naive Fibonacci. Stop at n = 30; the table cannot reach 100.
Find the crossover: try n = 100, 200, 400 in the timing loop and see where merge overtakes insertion. Real libraries hard-code a number found exactly this way.
Feed the timing loop an already sorted list. Insertion sort's best case is O(n) and it wins at every size — complexity classes describe worst cases unless someone says otherwise.
Where this runs
Real CPython, compiled to WebAssembly and running on your own machine — nothing is uploaded. The first run takes a few seconds while the interpreter downloads; after that it is immediate. Need more room, or want to paste your own attempt? Use the Python compiler.
Check yourself
0 of 3
Answer without scrolling back up.
Big-O describes:
It is a statement about growth, not about wall-clock time. Hardware changes the constant; it does not change the shape of the curve.
Which is O(1)?
Indexing computes an address and jumps to it, taking the same time whether the array holds ten items or ten million.
For n = 20, an O(n^2) algorithm may well beat an O(n log n) one. Why?
Asymptotic notation describes behaviour as n grows large. This is exactly why real sort implementations switch to insertion sort for small partitions.
Cheat sheet
Big-O Notation and Time Complexity
How does an algorithm's cost grow as the input grows? Race the six complexity classes against each other and watch the ones that look fine at n=10 become impossible at n=1000.
Introduction to Algorithms, chapter 3: Growth of FunctionsCormen, Leiserson, Rivest & Stein
About the author
Ashish Jangra builds and maintains VizLearn. Every module here is written and the visualisation behind it hand-built, so the numbers in a readout come from the same code that draws the picture. Corrections are genuinely welcome and get priority over everything else — if a page states something wrong, or an animation misrepresents what the algorithm does, get in touch.