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.

Functions0%

Loops0%

Explanation

Big-O notation 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 complexities (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 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 logic

Why 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 operations

Next in Algorithms & Data Structures

Arrays & Hash Maps

Continue

Unlocks

Arrays & Hash Maps Sorting Algorithms Recursion Patterns Binary Search