Big O Notation Explained: Time and Space Complexity

What Big O means

Big O describes how the work an algorithm does grows as the input size n grows. It does not measure seconds. It answers the question: "If the data becomes ten times larger, how much slower or hungrier will this code get?"

Two rules make it simple:

• Constants are dropped: 2n and n + 100 are both O(n).
• Only the fastest-growing term matters: n^2 + n is O(n^2).

Usually Big O is quoted for the worst case. Time complexity counts operations, space complexity counts extra memory.

The five complexities you meet most often

O(1): constant

The work does not depend on n.

def first(items):
    return items[0]

prices = {"apple": 3}
prices["apple"]  # dictionary lookup is O(1) on average

O(log n): logarithmic

Each step cuts the remaining data in half. Typical example: binary search in a sorted list.

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

O(n): linear

One pass over the data.

def total(items):
    s = 0
    for x in items:
        s += x
    return s

O(n log n): linearithmic

The cost of efficient general-purpose sorting, such as merge sort or the built-in sorted() in many languages.

O(n^2): quadratic

A loop inside a loop over the same data.

def has_duplicates(items):
    for i in range(len(items)):
        for j in range(i + 1, len(items)):
            if items[i] == items[j]:
                return True
    return False

How fast they grow

Approximate number of operations for different input sizes:

On ten items every option is fast. On a million items, quadratic code does a trillion steps, which is the difference between an instant response and a request that never finishes.

How to estimate your own function

1. Define n: what grows? Number of users, rows, characters.
2. Simple statements are O(1).
3. A loop over n multiplies the body by n.
4. Nested loops multiply: two nested loops over n give O(n^2).
5. Sequential blocks add up, then keep the largest: O(n) + O(n^2) = O(n^2).
6. Halving each step gives O(log n).
7. Check hidden costs: x in list is O(n), x in set is O(1) on average; slicing and copying are O(n).

A classic improvement of the duplicate check above:

def has_duplicates(items):
    seen = set()
    for x in items:
        if x in seen:
            return True
        seen.add(x)
    return False

Time drops from O(n^2) to O(n), but space grows from O(1) to O(n) because of the set. This time-for-memory trade-off is one of the most common decisions in practice.

Common mistakes

• Calling a function O(n) while it calls O(n) code inside a loop: that is O(n^2).
• Database queries in a loop: N queries instead of one are often the real bottleneck in web apps.
• Ignoring constants completely: for small n, a "worse" algorithm with a tiny constant can be faster. Measure when in doubt.
• Optimising code that runs on ten items: Big O matters where data grows.