Big-O Notation
Measure algorithm efficiency — time and space complexity
Knowledge Debt detected
You can study this freely — but your score may plateau if these foundations have gaps. The Mastery badge requires them to be solid.
Explanation
describes how an algorithm's runtime (or memory use) grows as the input size grows. It's the language engineers use to reason about performance at scale.
The most common :time-complexity[How the runtime of an algorithm increases as the input size grows, expressed using Big-O notation]s (best to worst):
| Notation | Name | Example | 1000 items | |---|---|---|---| | O(1) | Constant | Dict lookup | 1 op | | O(log n) | Logarithmic | Binary search | ~10 ops | | O(n) | Linear | Loop through list | 1,000 ops | | O(n log n) | Linearithmic | Merge sort | ~10,000 ops | | O(n²) | Quadratic | Nested loops | 1,000,000 ops | | O(2ⁿ) | Exponential | Naive recursion | astronomical |
Reading code for complexity:
python # O(1) — doesn't grow with input def get_first(lst): return lst[0] # O(n) — one loop def find_max(lst): m = lst[0] for x in lst: # n iterations if x > m: m = x return m # O(n²) — nested loops def has_duplicates(lst): for i in range(len(lst)): for j in range(i + 1, len(lst)): # n * n/2 ≈ n² if lst[i] == lst[j]: return True return False # O(n) — same problem with a set def has_duplicates_fast(lst): return len(lst) != len(set(lst)) # O(n) time, O(n) space
Dropping constants and lower terms:
O(2n) → O(n), O(n² + n) → O(n²). Big-O describes the growth *shape*, not the exact count.
:space-complexity[How much additional memory an algorithm uses relative to the input size, expressed using Big-O notation] — how much extra memory: ``python # O(1) space — no extra memory def sum_list(lst): total = 0 for x in lst: total += x return total # O(n) space — new list same size def doubled(lst): return [x * 2 for x in lst]
Examples
Identifying complexity in real code
The same question answered in O(n) vs O(1) — just by choosing a set over a list
# What's the complexity of each?
# 1. Dictionary lookup — O(1)
cache = {"a": 1, "b": 2}
value = cache.get("a") # O(1) regardless of dict size
# 2. List contains — O(n)
items = [1, 2, 3, ..., 1000]
exists = 999 in items # scans up to every element
# 3. Set contains — O(1) average
items_set = set(items)
exists = 999 in items_set # hash lookup, O(1)
# 4. Sorting — O(n log n)
sorted_items = sorted(items)
# Key insight: choosing the right data structure
# changes complexity without changing the algorithm logicWhy O(n²) breaks at scale
O(n²) vs O(n) — 5000x difference at n=10,000
import time
def find_pairs_slow(lst): # O(n²)
pairs = []
for i in range(len(lst)):
for j in range(i + 1, len(lst)):
if lst[i] + lst[j] == 0:
pairs.append((lst[i], lst[j]))
return pairs
def find_pairs_fast(lst): # O(n)
seen = set()
pairs = []
for x in lst:
if -x in seen:
pairs.append((-x, x))
seen.add(x)
return pairs
# At n=10_000:
# slow: ~50 million comparisons
# fast: ~10_000 operationsHow well did you understand this?
Next in Algorithms & Data Structures
Arrays & Hash Maps