Complexity Analysis Concepts

Complexity analysis describes how much more time and memory an algorithm needs as its input grows. A measurement like "this takes 0.3 seconds" depends on the machine, the language and the data, but a property like "doubling the input quadruples the running time" holds almost everywhere. Complexity analysis is about that shape of growth. This chapter covers input size, asymptotic notation (O, Ω, Θ), best, average and worst cases, and the vocabulary used in the rest of the guide.

Input size n

Analysis starts by deciding what "size" means. For a list it is the number of elements, for a string its length. Graphs usually need two variables, V vertices and E edges, and comparing two strings uses both lengths m and n.

Be careful with functions that take a single integer. The input size is the number of digits (bits) needed to write the number, not its value. Trial division up to √n is O(√n) in the value n, but O(2^(b/2)), exponential, in the bit length b.

Asymptotic notation: O, Ω, Θ

• Big-O (upper bound): f(n) = O(g(n)) if there are positive constants c and n0 such that f(n) ≤ c·g(n) for every n ≥ n0. f grows no faster than g.
• Big-Omega (lower bound): f(n) = Ω(g(n)) if f(n) ≥ c·g(n) under the same conditions. f grows at least as fast as g.
• Big-Theta (tight bound): f(n) = Θ(g(n)) if both hold. f grows at the same rate as g.

For example, f(n) = 3n² + 5n + 20 satisfies 3n² ≤ f(n) ≤ 28n² for n ≥ 1, so it is Θ(n²). Saying O(n³) is technically true but loose. In everyday speech, "this is O(n²)" usually means Θ.

We drop constants and lower-order terms because the highest-order term dominates as n grows. You can check the ratio yourself:

def f(n):
    return 3 * n * n + 5 * n + 20

for n in (10, 100, 1_000, 10_000):
    print(n, f(n), round(f(n) / (n * n), 4))
# 10 370 3.7
# 100 30520 3.052
# 1000 3005020 3.005
# 10000 300050020 3.0005

The ratio approaches 3, so f eventually behaves like a constant multiple of n². That constant changes with hardware and implementation, so the notation leaves it out.

Cases and bounds are different questions

A common misconception is "O means worst case, Ω means best case". They answer two separate questions:

• Which inputs are we looking at? Best case, average case, worst case.
• How do we describe that running time? Upper bound O, lower bound Ω, tight bound Θ.

Linear search finishes after one comparison when the target is first (best case Θ(1)) and needs n comparisons when it is last or missing (worst case Θ(n)). If the target is equally likely to be anywhere in the list, the average is (n + 1) / 2 comparisons, which is still Θ(n).

def linear_search(items, target):
    comparisons = 0
    for i, x in enumerate(items):
        comparisons += 1
        if x == target:
            return i, comparisons
    return -1, comparisons

data = [7, 3, 9, 4, 1]
print(linear_search(data, 7))   # (0, 1)  best case
print(linear_search(data, 1))   # (4, 5)  last element
print(linear_search(data, 8))   # (-1, 5) missing = worst case

The worst case is the usual default: you rarely control the input, so "it never takes longer than this" is the most useful guarantee.

Space as well as time

Space complexity measures how the extra memory grows with n. Memory beyond the input itself is called auxiliary space. Many problems let you trade one for the other.

def has_duplicate_slow(items):      # time O(n²), auxiliary space O(1)
    for i in range(len(items)):
        for j in range(i + 1, len(items)):
            if items[i] == items[j]:
                return True
    return False

def has_duplicate_fast(items):      # time O(n) on average, auxiliary space O(n)
    seen = set()
    for x in items:
        if x in seen:
            return True
        seen.add(x)
    return False

When to use it

• Choosing between approaches before writing code, based on the expected input size
• Working backwards from a coding interview's time limit and input range to the complexity you need
• Spotting hidden costs in code review, such as in list inside a loop or repeated sorting
• Estimating whether a service will survive ten times more data

Vocabulary

Summary

• Complexity analysis looks at the shape of growth, not absolute time.
• O is an upper bound, Ω a lower bound, Θ both; constants and lower-order terms are dropped.
• Best, average and worst case are about which input; O, Ω and Θ are about how to bound it.
• Time and space can be traded, so consider both.