Big O notation describes how the number of steps an algorithm takes grows as its input grows, leaving out the speed of the computer. This page builds it from scratch: count the steps of a few searches on an array, put the counts on a chart, and watch O(1), O(log n), O(n) and O(n²) appear. No programming background is needed.
Big O notation describes how the number of steps an algorithm takes grows with the size of its input, n. It leaves out the speed of the computer and keeps only the shape of the growth, so it tells in advance whether a program stays fast when its data grows a thousandfold.
Why Big O?
All steps as text
Programs keep their data in data structures. The simplest one is an array: a row of elements, each holding a value. This array holds 8 numbers.
We read values from an array, search it, insert into it and delete from it. Each of these operations is work for the computer, and work takes time.
When the array grows, some operations take longer and others don't. Big O notation describes exactly this: how the work grows as the data grows.
The work is done by an algorithm: a step-by-step method for a task, such as finding a value. An array lets us see every step, because each one looks at an element.
Why count steps, not seconds?
The same program runs at different speeds on different devices, so seconds measure the device as much as the algorithm. A count of steps is the same everywhere. The players below stack every step as a block, and the blocks grow into a chart.
The same search through 8 elements: 4 ms on an old phone, 1 ms on a new one, and the same 8 steps on both, one for each element looked at.
What does O(1) mean? Constant time
O(1): constant time
All steps as text
The number of elements is called n; this array has n = 8. Big O describes how the number of steps grows as n grows.
Each element has an index: its position, counted from 0. The small numbers above the elements are their indices.
Task: read the element at index 5. The elements lie side by side in memory, so the computer works out where element 5 is and goes straight there. One step, one block.
Now an array twice as long, n = 16. Reading index 5 is still one step: finding an element by its index does not depend on the length.
We have two measurements: 1 step at n = 8 and 1 step at n = 16. A chart shows them together: n runs across, steps go up, and each column stands at its n.
Both columns are one step tall, and a column for any other n would be too: the line through them is flat. Steps that don't grow with n are constant time, written O(1).
An operation is O(1) when its steps don't depend on n. Reading an array element by its index is the classic example: its address is computed from the index, not searched for (how arrays sit in memory).
What does O(n) mean? Linear time
Linear search checks the elements one by one, so its steps grow in proportion to n. Big O usually states the worst case: here the value is in the last element, or not there at all.
O(n): linear time
All steps as text
New task: find 58. The values are in no particular order, so 58 could be anywhere. All we can do is check the elements one by one from the left. This is linear search.
Each check is a step and adds a block. 58 is in the last element: 8 steps. A value that isn't in the array also takes 8, because only after checking every element do we know.
With n = 16, and the value we want, 97, in the last element, the search takes 16 steps. Twice the elements, twice the steps.
On the chart, the two columns rise with n, and the line through them is straight. Steps that grow in proportion to n are linear time, written O(n).
Had 58 been first, one step would have been enough: the best case. Big O usually describes the worst case, which is a promise: linear search never needs more than n steps.
What does O(log n) mean? Logarithmic time
Binary search needs sorted values, and each look rules out half of what is left. Doubling the array adds a single step, so a million sorted elements take about 20.
O(log n): logarithmic time
All steps as text
Linear search had to check the elements one by one, because 58 could be anywhere. Can a search do better?
It can, if the values are in order. Here is the same array, sorted from smallest to largest. (Sorting takes steps of its own; the sorting topics count them.)
Binary search starts in the middle. 8 elements have two middles, and we take the left one: index 3, which holds 31. 31 is less than 58, and everything to its left is smaller still.
So 58 can only be to the right. One step has ruled out half of the array: the dimmed elements no longer need checking.
Now the same with the four that are left. Their left middle, index 5, holds 44, and 44 is less than 58 too.
So 37 and 44 are ruled out as well. Two elements are left.
Of the last two, the left one is 52, at index 6. 52 is less than 58 as well.
52 is ruled out. One element is left.
The last look finds 58 at index 7: 4 steps. Linear search needed 8.
Now twice as many: the same 8 values and 8 larger ones, n = 16. This time we look for 97, the largest.
16 elements have two middles too; the left one, index 7, holds 58. 58 is less than 97.
So the whole left half, indices 0 to 7, is ruled out. 8 elements are left.
The middle of the remaining eight is 74, at index 11. 74 is less than 97.
Indices 8 to 11 are ruled out. 4 elements are left.
The middle of the last four is 85, at index 13: still less than 97.
Indices 12 and 13 go. 2 elements are left.
Of the last two, the left one is 91, at index 14: less than 97 again.
91 is ruled out. One element is left.
The fifth look finds 97: 5 steps. Doubling the array added only one step, because every step halves what is left.
16 elements can be halved 4 times before one is left: 16, 8, 4, 2, 1. This count is the logarithm of n, written log₂ n. One step per halving, plus a last look: 4 + 1 = 5.
On the chart, the steps barely rise. Steps that grow like log n are logarithmic time, O(log n): even a million sorted elements take only about 20 steps.
What does O(n²) mean? Quadratic time
Comparing every element with every other one takes n(n − 1)/2 comparisons: about half of an n × n grid of pairs. Big O drops constant factors such as that half (see the rules), so this is O(n²): twice the elements, four times the work.
O(n²): quadratic time
All steps as text
New task: does any value appear twice? The simplest way compares every element with every other. The grid has a square for each pair: row 1, column 4 compares element 1 with element 4.
Element 0 is compared with the 7 elements after it. Each comparison is a step and lights one square: 7 steps.
Then element 1 with the 6 after it, element 2 with the next 5, and so on: 7 + 6 + 5 + 4 + 3 + 2 + 1 = 28 comparisons. No value appears twice.
Why only half the grid? Comparing 1 with 4 is the same as comparing 4 with 1, and an element is never compared with itself. So of the 8 × 8 = 64 squares, (64 − 8) / 2 = 28 are lit: about half of n × n.
With 16 elements the grid has 16 × 16 = 256 squares, and the lit half is 120 pairs. Twice the elements, about four times the steps: the grid grows in both directions.
Put on the chart, these columns don't fit: 28 and 120 steps run off the top.
Zoomed out, the steps shoot up while the other lines stay low. The steps are about half of n × n, so doubling n multiplies them by four: quadratic time, written O(n²).
O(n log n) and O(2n)
O(n log n) is the time of the fastest general sorting algorithms, such as merge sort and heap sort. O(2ⁿ) doubles with every extra element and is only practical for very small inputs.
O(n log n) and O(2ⁿ)
All steps as text
The chart now shows four growth rates. Two more are common enough to know.
Between O(n) and O(n²) lies O(n log n): about log n steps for each of the n elements. The fastest general sorting algorithms, such as merge sort and heap sort, take this time.
Some algorithms double their work with every extra element: O(2ⁿ). Trying every combination of just 30 items already takes over a billion steps.
What does O(n log n) mean?
It means the steps grow like n × log n: about log n steps for each of the n elements. That grows faster than O(n), by a factor of log n, and far slower than O(n²): at a million elements, about 20 million steps against a million at O(n) and a trillion at O(n²).
Big O growth rates compared
The six growth rates on one chart, then in numbers. At a billion steps per second, a million elements take a millisecond at O(n) and about 17 minutes at O(n²).
Growth rates side by side
All steps as text
Here are all six together. The steeper the curve, the faster the work grows. For small n the curves are close and even cross; what matters is how they grow for large n.
The table gives the steps at three sizes. At n = 10, no class needs more than 100. At a million elements, O(log n) needs about 20 steps and O(n²) a trillion.
At a billion steps a second, a million elements take 1 millisecond at O(n), but about 17 minutes at O(n²). A faster computer can't make up for a faster-growing algorithm.
Rules for simplifying Big O
Big O keeps only how the steps grow, so constant factors and smaller terms are dropped. Steps done one after another add up; a loop inside a loop multiplies.
Rules for simplifying
All steps as text
Big O has a few rules for simplifying. To see the first, take a new task: find the smallest value, then the largest.
The first pass looks at every element, keeping the smallest seen so far. 8 looks, 8 steps: the smallest is 18.
The second pass looks at every element again, this time for the largest: 8 more steps, in orange. The largest is 58.
Two passes, one after the other, and their steps add up: 8 + 8 = 16, that is 2n.
2n still doubles when n doubles, so it grows like n: O(n). Big O drops constant factors like this 2, because they don't change how the steps grow.
The duplicate check made n(n − 1)/2 = n²/2 − n/2 comparisons. At n = 1 000 the n/2 part is just 0.1% of them, so Big O keeps only the fastest-growing term: O(n²).
In code, repeating a step for each element is a loop. A loop inside another loop multiplies: n steps for each of n elements makes n × n, O(n²). The duplicate check fills half the square: still O(n²).
Space complexity
The same notation measures memory: how much an algorithm needs besides its input, its auxiliary space.
Space complexity
All steps as text
So far we counted steps, which measure time. Big O measures memory the same way: how much extra memory an algorithm needs as n grows.
To find the largest value we keep one extra box, max, holding the largest value seen so far. One box for any n: O(1) space.
A copy of the array needs n more boxes, so its memory grows with n: O(n) space.
Big O in short
The growth rates from the slowest-growing to the fastest-growing, each with an example from this topic.
The formal definition of Big O
A function f(n) is O(g(n)) if there are a constant c greater than zero and a size n0 such that f(n) is at most c times g(n) for every n from n0 on.
For example, 2n + 3 is at most 3n for every n from 3 on, so 2n + 3 is O(n), with c = 3 and n0 = 3.
Big O is an upper bound
3n + 5 never exceeds n2 from n = 5 on, so it is also O(n²). By convention, the smallest class that fits is the one stated: 3n + 5 is O(n).
Big O, Big Omega and Big Theta
Big Omega, Ω, is a lower bound: f(n) is at least c times g(n) from some n0 on. Big Theta, Θ, means both at once: the function grows like g(n), up to constant factors. Each of the three can describe any case: the best, the average or the worst.
Best, worst and average case
Linear search is lucky when the value is first (one step) and unlucky when it is last or missing (n steps). Big O usually states the worst case, a guarantee for any input, unless another case is named: the best, the average, or the amortized cost over a sequence of operations.
Why the base of the logarithm doesn't matter
Changing the base of a logarithm only multiplies it by a constant: log2n is about 3.3 times log10n. Constants are dropped, so Big O writes just log n. Binary search counts halvings, which is log2n.
Big O cheat sheet
Class
Name
Examples
O(1)
constant
reading an array element by its index; a hash table lookup, on average
Keep only the fastest-growing term: n2 + n is O(n²).
Steps one after another add: a pass over n elements, then another, is O(n).
A loop inside a loop multiplies: n steps for each of n elements is O(n²).
A loop that halves its range each time runs about log n times.
Five of these examples are on GitHub as code, one function each, in Python, Java and C++: reading an element by its index (O(1)), binary search (O(log n)), linear search (O(n)), comparing every pair (O(n²)) and trying every combination of n items (O(2ⁿ)).
Related topics
Array: why reading by index is O(1), and why appending is O(1) amortized.
Binary Search Tree: search in O(log n) while the tree stays balanced, O(n) when it doesn't.