Big-O NotationTime and space complexity

01Why it exists

Reach for it when you see:The complexity of this code, how much slower it gets with ten times the data, whether it can be faster, what n actually is.

02The core idea

Big-O answers one question: as the input size n grows, how fast does the amount of work grow with it? It is not a number of seconds but the shape of that growth. O(n) means the growth is a straight line, O(n²) is a parabola, and O(log n) is almost flat.

Because only the shape matters, Big-O comes with two simplifying rules: drop the constants (3n and n are both O(n)) and keep only the largest term (n² + n is O(n²)). Together they let the same algorithm, written on different machines in different languages, be compared using one notation.

Space complexity describes the extra memory used in exactly the same way. The classic trade is to spend space to buy time: add a hash table and an O(n²) comparison becomes O(n).

The common complexities, fastest to slowest: O(1) → O(log n) → O(n) → O(n log n) → O(n²) → O(2ⁿ) → O(n!). The first four are fine with millions of items; the last three stop being usable very quickly, and the demo below lets you feel that for yourself.

03The algorithm

1. 1Work out what "n" is: array length, string length, node count. Two inputs means two variables, as in O(m·n).
2. 2Look at the nesting and the range of the loops: one loop over n is O(n), two nested loops over n each are O(n²), and a loop that halves the range each time is O(log n).
3. 3Look at what the functions you call actually do: calling an O(n) function inside a loop makes the whole thing O(n²). A built-in sort is O(n log n), and in is O(n) on a list but O(1) on a set.
4. 4Add the pieces up, then drop the constants and the smaller terms: 2n² + 5n + 100 → O(n²).
5. 5Quote the worst case by default. If the problem emphasises the average or amortised cost, say so separately.

04Interactive demo

Change n and compare the operation counts for seven complexity classes. The right-hand column assumes one nanosecond per operation and converts that into how long you would actually wait.

05Code

The same "are there any duplicates?" problem, written two ways that are a factor of n apart. As you read the code, practise counting the complexity of each piece with the steps above.

# O(1): the same amount of work no matter how big n is
def first(items):
    return items[0]

# O(n): the loop runs n times
def total(items):
    s = 0
    for x in items:
        s += x
    return s

# O(n²): two nested loops, each running n times
def has_duplicate_slow(items):
    n = len(items)
    for i in range(n):
        for j in range(i + 1, n):
            if items[i] == items[j]:
                return True
    return False

# O(n): a hash set replaces the inner loop, taking space from O(1) to O(n)
def has_duplicate(items):
    seen = set()
    for x in items:
        if x in seen:
            return True
        seen.add(x)
    return False

# O(log n): every step halves the range
def binary_search(sorted_items, target):
    lo, hi = 0, len(sorted_items) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if sorted_items[mid] == target:
            return mid
        if sorted_items[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

06Practice

The point of these is not to solve them but to write the brute-force version first, work out its complexity, and then find a way to drop it by one order.

• LeetCode 217Contains Duplicate (O(n²) → O(n))Easy
• LeetCode 1Two Sum (O(n²) → O(n))Easy
• LeetCode 704Binary Search (O(n) → O(log n))Easy
• LeetCode 189Rotate Array (O(n) time, O(1) space)Medium