Data structures and algorithms

Lesson 1 of 81965–19768 min

Complexity and Big-O

In 1965 Juris Hartmanis and Richard Stearns published "On the computational complexity of algorithms", which classified problems by how the time needed to solve them grows with the size of the input. The paper gave the field its name, and in 1993 it earned them the Turing Award.

The notation came from number theory, and by the 1970s it was used loosely and inconsistently. In 1976 Donald Knuth wrote a short letter to SIGACT News proposing that computer scientists use O for upper bounds, Ω for lower bounds and Θ for both. That is the vocabulary every algorithms exam still uses.

Count steps, not seconds

The same program runs at different speeds on different machines, so seconds tell you little about the algorithm. Instead we count basic operations (comparisons, assignments, arithmetic) as a function of the input size n, and ask how that count grows. We usually study the worst case, the input that makes the algorithm work hardest, because it is a guarantee. Searching an unsorted list of n items for a missing value takes n comparisons; binary search in a sorted list takes about log₂ n.

O, Ω and Θ

f(n) = O(g(n)) if there are constants c > 0 and n₀ such that f(n) ≤ c·g(n) for every n ≥ n₀: g is an upper bound on growth, up to a constant factor and for large enough n. Ω(g(n)) is the matching lower bound (f(n) ≥ c·g(n)), and Θ(g(n)) means both at once. So 3n² + 5n + 7 is Θ(n²): constants and lower-order terms do not change the growth rate. To prove 3n² + 5n + 7 = O(n²), take c = 4 and n₀ = 7: for n ≥ 7, 5n + 7 ≤ n², so the whole sum is at most 4n².

StepsAt 1 million steps/s
O(1)1instant
O(log n)4instant
O(n)16instant
O(n log n)64instant
O(n²)256instant
O(2ⁿ)65,53666 ms
O(1), O(log n), O(n), O(n log n), O(n²) and O(2ⁿ) as n grows. The gap between the curves is the whole point.

The ladder to remember is 1 < log n < n < n log n < n² < n³ < 2ⁿ < n!. For n = 1,000,000, log₂ n is about 20, n log₂ n about 2 × 10⁷, and n² is 10¹², which at a billion simple operations per second is over a quarter of an hour instead of a fraction of a second. Space complexity counts extra memory the same way. Amortised cost averages over a sequence of operations: one append to a Python list occasionally copies the whole array, but n appends cost O(n) in total, so each is amortised O(1).

python
def has_duplicate_slow(xs):     # O(n²): compares every pair
    n = len(xs)
    for i in range(n):
        for j in range(i + 1, n):
            if xs[i] == xs[j]:
                return True
    return False

def has_duplicate_fast(xs):     # O(n) on average: one pass and a set
    seen = set()
    for x in xs:
        if x in seen:
            return True
        seen.add(x)
    return False

def halvings(n):                # O(log n): n is halved each time
    steps = 0
    while n > 1:
        n //= 2
        steps += 1
    return steps
The same question answered in O(n²) and O(n), and a loop whose variable halves: the signature of O(log n).

Worked exercise

Count the comparisons

In the worst case (no duplicates), how many times does has_duplicate_slow evaluate xs[i] == xs[j] for n = 1,000? What is its order of growth, and what is halvings(1_000_000)?

Try it first, then reveal the solution one step at a time.

Key terms

Asymptotic analysis
Describing how cost grows as the input size tends to infinity, ignoring constant factors.
Big O
An upper bound: f(n) ≤ c·g(n) for all n beyond some n₀.
Big Omega
A lower bound: f(n) ≥ c·g(n) for all n beyond some n₀.
Big Theta
A tight bound: both O(g(n)) and Ω(g(n)).
Worst case
The input of a given size that makes the algorithm do the most work.
Amortised cost
The average cost per operation over a worst-case sequence of operations.

Check what you learned

  1. 1.What is the tight bound of f(n) = 3n² + 100·n·log n + 7?

  2. 2.Which of these grows fastest as n tends to infinity?

  3. 3.Roughly how many comparisons does binary search need in the worst case on 1,000,000 sorted items?

Practise it for the exam

Sources