Big-O notation scares off a lot of self-taught developers because it’s usually introduced with formal mathematical definitions before anyone explains why it’s actually useful. Stripped of the jargon, it’s just a way to describe how an algorithm’s runtime grows as input size grows.
The Notations That Actually Come Up
- O(1) — constant time: array index access, hash map lookup
- O(log n) — logarithmic: binary search, balanced tree operations
- O(n) — linear: a single loop over a list
- O(n log n) — the realm of good sorting algorithms (merge sort, quicksort’s average case)
- O(n²) — quadratic: nested loops over the same data, naive duplicate detection
Seeing It in Code
# O(1): constant time regardless of list size
def get_first(items):
return items[0]
# O(n): time grows linearly with input size
def contains(items, target):
for item in items:
if item == target:
return True
return False
# O(n^2): nested loop over the same data
def has_duplicates_naive(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): the same problem, solved with a set instead
def has_duplicates_fast(items):
seen = set()
for item in items:
if item in seen:
return True
seen.add(item)
return False
Why This Matters in Practice
The difference between O(n) and O(n²) is invisible with 10 items and catastrophic with 10 million — an O(n²) duplicate check that takes a millisecond on a test dataset can take hours on production data. Big-O isn’t about precise timing; it’s about recognizing which algorithms will fall over as your data grows, before you find out the hard way in production.