Big-O notation describes how an algorithm’s running time (or memory) grows as the input size n grows, ignoring constants and smaller terms.
Common complexities
| Big-O | Name | Example |
|---|---|---|
| O(1) | Constant | Reading an array element by index |
| O(log n) | Logarithmic | Binary search in a sorted list |
| O(n) | Linear | Scanning a list once |
| O(n log n) | Linearithmic | Merge sort |
| O(n²) | Quadratic | Comparing every pair with nested loops |
Example: finding duplicates
# O(n²): compare every pair
def has_duplicate_slow(items):
for i in range(len(items)):
for j in range(i + 1, len(items)):
if items[i] == items[j]:
return True
return False
# O(n): remember what you've seen in a set
def has_duplicate_fast(items):
seen = set()
for x in items:
if x in seen:
return True
seen.add(x)
return False
For a million items, the first version can make about 500 billion comparisons. The second makes about a million set lookups.
Rules of thumb
- Drop constants: O(2n) is O(n).
- Keep the dominant term: O(n² + n) is O(n²).
- Loops in sequence add; nested loops multiply.
Practice
What is the complexity of a loop that halves n until it reaches 1?
O(log n), because the number of halvings is about log₂ n.