Big O Notation Explained (Time and Space Complexity)

Big O notation is the language programmers use to describe how an algorithm's running time (or memory use) grows as the input size grows. It doesn't measure exact seconds — it measures the shape of growth, so you can compare two approaches without running a stopwatch. "This algorithm is O(n)" means its work scales roughly linearly with input size n; "this one is O(n²)" means the work scales with the square of n — and on large inputs, that difference is enormous.

Big O almost always describes the worst case, because that's the scenario your code has to survive. An algorithm that's fast on average but catastrophically slow on one particular input shape is still a risk in production.

The Common Complexity Classes

These are listed from fastest to slowest growth, with n representing the size of the input:

# O(1) — Constant time: same speed regardless of input size
def get_first(items):
    return items[0]

# O(log n) — Logarithmic: halves the problem each step (e.g. binary search)
def binary_search(items, target):
    low, high = 0, len(items) - 1
    while low <= high:
        mid = (low + high) // 2
        if items[mid] == target:
            return mid
        elif items[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1

# O(n) — Linear: one pass through the input
def contains(items, target):
    for item in items:
        if item == target:
            return True
    return False

# O(n log n) — Linearithmic: typical of efficient sorting algorithms
sorted_items = sorted([5, 3, 1, 4, 2])  # Python's sort is O(n log n)

# O(n^2) — Quadratic: nested loops over the same input
def has_duplicate_pair(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(2^n) — Exponential: doubles with every additional input element
def fibonacci_naive(n):
    if n <= 1:
        return n
    return fibonacci_naive(n - 1) + fibonacci_naive(n - 2)

Output:

These functions aren't printed directly here — the point is their growth rate, not a specific result. Try calling has_duplicate_pair() on a 10-item list vs a 10,000-item list to feel the O(n²) slowdown yourself.

Why Worst Case Dominates the Conversation

Consider linear search vs binary search: linear search is O(n) because, in the worst case, the target is the very last element checked (or isn't there at all). Binary search is O(log n) because each comparison eliminates half the remaining elements — searching a billion items takes only about 30 steps. That gap between "scan everything" and "eliminate half each time" is the entire reason Big O notation exists: it captures a structural difference that no amount of hardware upgrades can close.

A Visual Intuition for Growth

If n = 1,000: O(log n) is about 10 operations, O(n) is 1,000 operations, O(n log n) is about 10,000, O(n²) is 1,000,000, and O(2^n) is a number with over 300 digits. This is why an O(n²) algorithm that feels instant while testing on 50 items can completely freeze on 50,000 — the growth isn't proportional, it compounds. Mastering Big O means training yourself to spot these patterns — nested loops, halving steps, branching recursion — directly in code, which is exactly what we cover next in analyzing algorithm complexity.

---