TL;DR:
Big O describes how the number of steps grows as the input size n grows, ignoring constant factors.
Constant O(1) does not grow, logarithmic O(log n) grows very slowly, linear O(n) grows in step with n, and quadratic O(n²) grows with its square.
Finding a name in a sorted list takes up to n steps with a scan but only about log₂ n with binary search.
You have a class list of 1,000 names in alphabetical order and need to find one. You could read from the top until you hit it, or open the list in the middle and decide which half to keep. Both work, but one needs up to 1,000 looks and the other needs about 10. Big O is the language for saying that precisely.
The idea in plain words
Big O notation describes how the number of steps an algorithm takes grows as the input size, n, grows. It ignores constants and small terms, because for large n only the fastest-growing part matters. An algorithm that takes 3n + 5 steps is simply O(n), and one that takes n² + 100n is O(n²).
By default, Big O talks about the worst case. For finding a name, the worst case is that it is last or not there.
The common growth rates
O(1), constant. The work does not depend on n. Looking up the item at position 5 in a list.
O(log n), logarithmic. Each step cuts the problem in half. Binary search on a sorted list.
O(n), linear. Work grows in step with n. Reading a list from the top.
O(n²), quadratic. Work grows with the square of n. Comparing every pair in a list.
Worked example: finding a name in a sorted list
Scan from the top. In the worst case you look at all n names. That is O(n).
Binary search. Look at the middle name. If your name comes earlier in the alphabet, discard the second half. Otherwise discard the first half. Repeat. Each look halves the list, so the number of looks is about log₂ n. That is O(log n).
List size n | Scan, worst case | Binary search, worst case | All pairs, about n²/2 |
|---|---|---|---|
8 | 8 | 4 | 28 |
16 | 16 | 5 | 120 |
1,024 | 1,024 | 11 | 523,776 |
1,048,576 | 1,048,576 | 21 | about 5.5 × 10¹¹ |
Check a row. For n = 1,024 = 2¹⁰, halving 1,024 gives 512, 256, 128, 64, 32, 16, 8, 4, 2, 1. That is 10 halvings, and one more look at the last remaining name makes 11. For all pairs, 1,024 × 1,023 ÷ 2 = 523,776. For n = 8 the worst case is 4 looks (8, 4, 2, 1 names left), and the number of pairs is 8 × 7 ÷ 2 = 28.
The big lesson is in the last row. When the list grows by a factor of about 1,000, from 1,024 to 1,048,576, the scan takes 1,024 times longer but binary search needs only 10 more looks.
Reading Big O from code
Here is a function that checks whether a list has two equal items.
def has_duplicate(items):
for i in range(len(items)):
for j in range(i + 1, len(items)):
if items[i] == items[j]:
return True
return False
print(has_duplicate([3, 1, 4, 1]))It prints True, because the two 1s match. In the worst case there are no duplicates, so every pair is checked once: n(n − 1)/2 comparisons. For n = 4 that is 4 × 3 ÷ 2 = 6. Two nested loops over the list give O(n²). If the list doubles to 8 items, the pairs grow to 8 × 7 ÷ 2 = 28, which is more than four times as many.
Why we drop constants
A scan that checks each name twice takes 2n steps. Another that checks once takes n. Both are O(n), since doubling n doubles the work in either case. Constants matter in practice, but they do not change how the algorithm scales, and scaling is what decides which algorithm survives on large inputs.
How to check your answer
Double n and see what happens to the steps. Linear doubles. Quadratic quadruples. Logarithmic adds one step.
Look for loops: one loop over n is O(n). A loop inside a loop, both over n, is O(n²).
Look for halving: a problem cut in half each time is O(log n).
Check the sorted-input requirement for binary search. On an unsorted list it fails.
Common mistakes
Thinking O(n) means exactly n steps. It means the growth is proportional to n.
Keeping lower terms.
n² + nis O(n²).Thinking a fast-growing O is always slower for small n. For small inputs, a simple O(n²) method can beat a clever one.
Mixing up the base of the logarithm. In Big O, the base only changes a constant, so O(log n) is enough.
Where you will use it next
Big O lets you compare any algorithms, from sorting to graph search. Binary search has its own article, binary search step by step, and the binary counting behind log₂ is explained in binary numbers and why computers use them.
Frequently asked questions
Is Big O the actual running time?
No. It describes how the time grows with input size. The actual time depends on the machine, the language and the constants.
Does Big O only describe the worst case?
It is most often used for the worst case, but you can also state an average or best case.
Get started
