Algorithms & Complexity

Understanding Big-O Notation

Big-O notation is how developers describe how an algorithm's cost scales with input size. Once you can read it fluently, you can compare implementations without running them.

Published April 10, 2026

Big-O notation answers a simple question: as the input to an algorithm grows, how does the number of operations (or memory used) grow with it? It doesn't measure exact time in milliseconds — it abstracts away hardware and implementation details to describe growth shape.

The "O" stands for "Order of" — order of magnitude. When you write O(n), you're saying that as n doubles, the work the algorithm does roughly doubles too. When you write O(n²), doubling n quadruples the work.

The common complexity classes

O(1) — constant time. The operation takes the same amount of time regardless of input size. Array index access is the canonical example:

items = [10, 20, 30, 40]
x = items[2]   # always one operation, regardless of list length

Hash table lookups are also O(1) on average. The key word is "on average" — in the worst case (many hash collisions), a lookup degrades to O(n). This distinction between average-case and worst-case matters in practice.

O(log n) — logarithmic time. The classic example is binary search. Each step of the algorithm eliminates half the remaining search space, so even on a list of a million items, binary search takes at most 20 steps (log&sub2;(1,000,000) ≈ 20).

def binary_search(arr, target):
    lo, hi = 0, len(arr) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

O(log n) algorithms are extremely efficient. Doubling the input only adds one more step.

O(n) — linear time. You must look at each element once. A single loop over an array is O(n).

def find_max(arr):
    best = arr[0]
    for x in arr:        # visits every element
        if x > best:
            best = x
    return best

O(n log n) — linearithmic time. Merge sort and heap sort are classic examples. This is the best achievable complexity for a general-purpose comparison sort. Doubling n slightly more than doubles the work, but it scales very well in practice.

O(n²) — quadratic time. Nested loops where both iterate over the input. Bubble sort is the textbook case:

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):           # O(n)
        for j in range(n - i - 1):  # O(n) nested
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]

With 100 items, that's roughly 10,000 operations. With 10,000 items, roughly 100 million. O(n²) algorithms quickly become impractical at scale.

O(2^n) — exponential time. Algorithms that try every possible subset. The naive recursive Fibonacci is a well-known example. Exponential algorithms are only usable for very small inputs.

How to read Big-O in practice

When analysing a function, look for loops. A single loop is usually O(n). A loop inside a loop is O(n²). A loop that halves the problem each iteration is O(log n). Recursive functions require a bit more thought — you need to count how many recursive calls you make and how big each subproblem is.

Drop constants and lower-order terms. O(3n + 50) simplifies to O(n). O(n² + n) simplifies to O(n²). Big-O is concerned with growth shape, not exact coefficients.

Best-case, worst-case, and average-case

A single algorithm can have different complexities depending on input. Quicksort has O(n log n) average-case performance but O(n²) worst-case (already-sorted input with a naive pivot strategy). Knowing which case you're analysing matters when you're choosing an algorithm for a specific workload.

In most practical discussions, when someone says "this algorithm is O(n log n)" they mean the worst-case or expected-case — check the context carefully.

Why it matters in daily work

The most common performance problem in application code is not a missing cache or a slow network call — it's accidentally writing O(n²) code where O(n) or O(n log n) was possible. A common example is searching a list inside a loop:

# O(n^2) — searching a list inside a loop
for user in users:
    if user in blocked_list:   # list search is O(n)
        skip(user)

# O(n) — use a set for O(1) lookups
blocked_set = set(blocked_list)
for user in users:
    if user in blocked_set:    # set lookup is O(1)
        skip(user)

At 1,000 users and 1,000 blocked IDs, the first version does up to one million comparisons. The second does about 2,000. Understanding Big-O is how you spot the difference before it becomes a production incident.