Complexity (Big-O)

What Big-O describes

Big-O is an upper bound on growth. It ignores the exact number of seconds and asks: when n doubles or grows tenfold, how much more work happens? Because it is an upper bound, an O(log n) algorithm is technically also O(n), though we normally state the tightest bound.

The usual growth classes, from slowest-growing to fastest-growing, are O(1), O(log n), O(n), O(n log n), O(n^2) and O(2^n).

Simplifying: drop constants and small terms

Keep only the fastest-growing term and discard constant multipliers. So 3n + 5 becomes O(n), and 5n^2 + 100n + 20 log n becomes O(n^2). For large n the biggest term dominates everything else.

For the same reason, log base does not matter: log2 n and log10 n differ only by a constant factor, so both are O(log n). A loop that runs a fixed 100 times inside a loop over n is still O(n), because 100 is a constant.

Example

Simplifying: drop constants and small terms

for i in range(n):        # n times
    for j in range(100):  # 100 times (constant)
        work()            # total 100n -> O(n)

Counting loops

One loop over n items is O(n). Two loops one after the other add up (n + n = 2n, so O(n)). Nested loops multiply: n times n is O(n^2). Loops over different inputs give O(n * m), not O(n^2).

If the inner loop depends on the outer variable, such as running i times, the total is 1 + 2 + ... + n, which is about n^2 / 2, still O(n^2). A loop that halves or doubles its variable each step runs about log n times. A doubling inner loop nested inside a loop over n gives O(n log n).

Example

Counting loops

i = n
while i > 1:
    i = i // 2   # halves each time -> O(log n)

for i in range(n):     # n times
    j = 1
    while j < n:       # log n times
        j = j * 2      # total O(n log n)

Best, worst and amortized cost

The worst case is the most work any input of size n can cause; the best case is the least. Linear search finds its target immediately in the best case (O(1)) but must check every item in the worst case, when the target is last or absent (O(n)). Unless told otherwise, Big-O usually means worst case.

Amortized cost averages over a sequence of operations. A dynamic array occasionally copies everything into a bigger array, so a single append can cost O(n). But resizes happen rarely when capacity doubles, so n appends cost O(n) in total and each append is amortized O(1).

Space and recursion

Space complexity counts extra memory used. Building a list of n items is O(n) space. Recursive calls use the call stack: a function that calls itself n times deep uses O(n) stack space, while one that halves the problem each call (like recursive binary search) goes only O(log n) deep.

Recursion also affects time. Halving the input and making one call gives O(log n). Making two calls on n - 1 gives O(2^n). Splitting into two halves and doing O(n) work to combine gives O(n log n).

Example

Space and recursion

def f(n):
    if n <= 1:
        return
    f(n // 2)   # one call, half the size -> O(log n) time and stack