Big O notation explained simply
7 min readUpdated
Big O notation describes how the running time (or memory) of an algorithm grows as the input grows. It lets you compare algorithms without timing them, and it is asked in A level, university modules and coding interviews.
The common complexities
| Big O | Name | Example |
|---|---|---|
| O(1) | Constant | Reading one item of a list by its index |
| O(log n) | Logarithmic | Binary search on a sorted list |
| O(n) | Linear | Linear search; adding up a list |
| O(n log n) | Linearithmic | Merge sort |
| O(n²) | Quadratic | Bubble sort; comparing every pair |
How to work it out from code
- A single loop over n items is O(n).
- A loop inside a loop, both over n items, is O(n²).
- Halving the problem on every step is O(log n).
- Keep only the biggest term and drop constants: 3n² + 5n + 2 is O(n²).
def total(items): # O(n): one pass
s = 0
for x in items:
s += x
return s
def has_pair_sum(items, t): # O(n²): every pair
for i in range(len(items)):
for j in range(i + 1, len(items)):
if items[i] + items[j] == t:
return True
return FalseBest, average and worst case
Big O usually means the worst case. Linear search is O(1) at best (the item is first) but O(n) in the worst case (it is last or missing).
Typical exam questions
- State the time complexity of binary search and explain why.
- Compare bubble sort and merge sort for a large list.
- Explain why an O(n log n) algorithm beats an O(n²) one as n grows.
Frequently asked questions
What does O(n) mean?
The time grows in proportion to the input size: twice as many items take about twice as long.
Why is binary search O(log n)?
Each comparison halves the part of the list still to search, so a list of n items needs about log2(n) steps.
Do I drop constants in Big O?
Yes. Big O describes growth, so 2n and n are both O(n), and n² + n is O(n²).
Learn it step by step
Practise this, step by step
Short lessons with quizzes, practice and interview questions, from your first program to job-ready.