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.
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.
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.
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 quotes the worst case, but not always the whole story. Quick sort is O(n log n) on average and O(n²) in the worst case — which is why implementations randomise the pivot. Linear search is O(1) if the target happens to be first and O(n) if it is last.
You will also see Ω (best case, a lower bound) and Θ (when best and worst match). In everyday use, "the complexity" means worst-case Big-O.
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.
Interactive Exploration Guide
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.
Key Takeaway
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.
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.