10. Algorithms and Complexity

An algorithm is a finite, precise procedure for solving a problem, and complexity theory measures how much time and memory that procedure needs as its input grows. This chapter shows how to specify algorithms and studies three basic families (searching, sorting, greedy), then develops the asymptotic notation O, Ω and Θ and uses it to analyze running time and space. It ends by separating tractable problems from intractable ones, which leads to P, NP and NP-completeness. These ideas tell you, before you write any code, whether an approach will scale to a million inputs or stall at fifty.

<a id="101-algorithm-basics"></a>

10.1 Algorithm Basics

This subchapter defines what an algorithm is and how to write one down precisely. It then studies three families of algorithms that recur throughout computing: searching, sorting, and greedy optimization.

Algorithm Specification and Pseudocode

Why. "Find the largest number in the list" is a clear instruction for a person, but it leaves questions open. What if the list is empty? If the largest value occurs twice, which one is meant? Should the answer be the value or its position? Before an algorithm can be implemented, proved correct (3.3) or analyzed (10.3), it must be stated so precisely that no step is ambiguous. It should also be stated independently of any programming language, so that the idea, not the syntax, is what you see.

What. An algorithm is a finite sequence of precise instructions for performing a computation or solving a problem. The word comes from al-Khwārizmī, the 9th-century Persian mathematician whose book on arithmetic brought decimal notation to Europe. An algorithm is expected to have the following properties:

Property	Meaning	Violated by
Input	Takes its input from a specified set	"Sort the data" with no statement of what the data is
Output	Produces output from a specified set: the solution	A procedure that prints nothing and returns nothing
Definiteness	Every step is precisely defined	"Pick a reasonable pivot"
Correctness	Produces the correct output for every valid input	A sort that mishandles duplicate keys
Finiteness	Halts after finitely many steps on every valid input	"While x ≥ 0, add 1 to x"
Effectiveness	Each step can be carried out exactly, in finite time	"If the decimal expansion of π contains a run of 10¹⁰⁰ zeros, …"
Generality	Applies to every input of the stated form, not just one instance	A procedure that only sorts the list [3, 1, 2]

Specification. A problem describes, for every possible input, which outputs are acceptable. One particular input is an instance of the problem. A specification states a precondition (what the algorithm may assume about its input) and a postcondition (what must hold for its output), exactly as in the correctness proofs of 3.3:

  Problem   MAXIMUM
  Input     integers a₁, a₂, …, aₙ with n ≥ 1                   (precondition)
  Output    an index i such that aᵢ ≥ aⱼ for every j            (postcondition)

This specification allows several correct outputs when the maximum value appears more than once. That is deliberate: a specification should demand exactly what the caller needs, and nothing more.

Pseudocode. Pseudocode sits between English and a programming language. It is precise enough to analyze, yet free of declarations, imports and error handling. This chapter uses the following conventions:

Construct	Pseudocode	Notes
Assignment	x := e	:= keeps assignment distinct from the equality test =
Conditional	if c then S₁ else S₂
Counted loop	for i := 1 to n	Runs exactly n times, so it always terminates
Conditional loop	while c	Termination needs a decreasing variant (3.2)
Procedure	procedure name(parameters)
Result	return x
Comment	{ … }
Blocks	Indentation

Arrays are indexed from 1 in pseudocode, as is usual in mathematics, and from 0 in Python.

Example.

procedure max_index(a₁, …, aₙ: integers)        { precondition: n ≥ 1 }
    best := 1
    for i := 2 to n
        if aᵢ > a_best then best := i           { strict >: the first maximum wins ties }
    return best                                 { postcondition: a_best ≥ aⱼ for all j }

def max_index(a):
    assert len(a) >= 1                          # precondition
    best = 0
    for i in range(1, len(a)):
        # loop invariant (3.3): a[best] is the maximum of a[0:i]
        if a[i] > a[best]:                      # strict >, so ties keep the earlier index
            best = i
    assert all(a[best] >= x for x in a)         # postcondition, checked at run time (a test, not a proof)
    return best

print(max_index([3, 9, 2, 9, 4]))               # 1   the first of the two 9s
print(max_index([-5]))                          # 0   a one-element list is its own maximum

The same algorithm can be described at three levels of detail:

Level	Written for	max_index at this level
English	People who want the idea	"Scan the list and remember the position of the largest value seen so far."
Pseudocode	People who will implement, prove or analyze it	The procedure above
Program	A machine	The Python function above

Analogy. A recipe is an algorithm only if every step is definite. "Add salt to taste" fails definiteness, while "add 5 g of salt" passes. "Bake until done" fails finiteness unless "done" is something you can check.

Key takeaways

• An algorithm is a finite sequence of precise instructions. It must be definite, correct, finite, effective and general.
• A specification is a precondition plus a postcondition. It may allow several correct outputs.
• Pseudocode exposes the logic of an algorithm without language-specific detail, and it is the usual starting point for correctness proofs and running-time analysis.
• Counted loops always terminate. A while loop needs a variant to prove that it terminates.

Practice

1. (Beginner) Which properties from the table does each procedure violate? (a) "Given an integer x ≥ 0, repeat x := x + 1 until x < 0." (b) "Output a number between 1 and 10." (c) "Output the list of all prime numbers."
2. (Intermediate) Write a specification and pseudocode for "find the second-largest distinct value" in a list of integers. Decide, and state in the precondition or postcondition, what happens when every element is equal. Give a loop invariant for your algorithm.
3. (Interview) You are asked to "remove duplicates from a sorted array in place". Before writing code, list the clarifying questions you would ask, and write the postcondition you agree on. Hint: what is returned (the new length?), what the first k positions must contain and in what order, and whether anything is guaranteed about positions after k.

Searching Algorithms

Why. "Is x in this collection, and where?" is one of the most common questions a program asks: dictionary lookups, database indexes, autocomplete, deciding whether a user name is taken. Two algorithms show how structure in the data changes the cost. Linear search assumes nothing about the data. Binary search requires sorted data, and in return it discards half of the remaining candidates with every comparison.

What. The search problem: given a sequence a₁, …, aₙ and a target x, return an index i with aᵢ = x, or report that there is none (by returning 0 in 1-indexed pseudocode, or −1 in Python).

Linear search compares x with a₁, a₂, … in turn and stops at the first match.

procedure linear_search(x, a₁, …, aₙ)
    for i := 1 to n
        if aᵢ = x then return i
    return 0                                     { x does not occur }

In the worst case (x is last, or missing) it makes n comparisons.

Binary search requires a₁ ≤ a₂ ≤ … ≤ aₙ. It keeps an interval of positions that must contain x if x occurs at all. It compares x with the middle element of the interval and keeps only the half that can still contain x.

procedure binary_search(x, a₁ ≤ … ≤ aₙ)
    lo := 1;  hi := n + 1                         { invariant: if x occurs, it is in a_lo … a_(hi−1) }
    while lo < hi                                 { variant: hi − lo, which strictly decreases }
        mid := ⌊(lo + hi) / 2⌋
        if a_mid = x then return mid
        else if a_mid < x then lo := mid + 1      { x cannot be at mid or to its left }
        else hi := mid                            { x cannot be at mid or to its right }
    return 0

Why ⌊log₂ n⌋ + 1 iterations suffice. Let L = hi − lo be the length of the interval. The midpoint leaves ⌊L/2⌋ positions on its left and ⌈L/2⌉ − 1 ≤ ⌊L/2⌋ on its right, so after one iteration the length is at most ⌊L/2⌋. After k iterations it is at most ⌊n/2ᵏ⌋, and the loop can run only while the length is at least 1. So there are at most ⌊log₂ n⌋ + 1 iterations: 20 for a million elements, 31 for two billion.

Trace. Searching for x = 19 (0-indexed, as in Python):

  index:    0   1   2   3   4   5   6   7   8   9
  value:    1   3   4   7   9  12  15  19  22  30

  lo=0  hi=10  mid=5   a[5]=12 < 19  →  lo = 6     [ ·  ·  ·  ·  ·  ·  15 19 22 30 ]
  lo=6  hi=10  mid=8   a[8]=22 > 19  →  hi = 8     [ ·  ·  ·  ·  ·  ·  15 19  ·  · ]
  lo=6  hi=8   mid=7   a[7]=19 = 19  →  found at 7

def linear_search(a, x):
    probes = 0
    for i, v in enumerate(a):
        probes += 1
        if v == x:
            return i, probes
    return -1, probes

def binary_search(a, x):
    lo, hi, probes = 0, len(a), 0                 # invariant: if x is in a, it is in a[lo:hi]
    while lo < hi:
        mid = (lo + hi) // 2                      # Python ints never overflow; in Java/C use lo + (hi - lo) / 2
        probes += 1
        if a[mid] == x:
            return mid, probes
        elif a[mid] < x:
            lo = mid + 1
        else:
            hi = mid
    return -1, probes

a = list(range(0, 2_000_000, 2))                  # one million sorted even numbers
for x in (0, 1_999_998, 7):                       # first element, last element, absent (odd)
    print(x, linear_search(a, x), binary_search(a, x))
# 0 (0, 1) (0, 20)
# 1999998 (999999, 1000000) (999999, 19)
# 7 (-1, 1000000) (-1, 20)

	Linear search	Binary search
Precondition	None	Sorted input with random access (an array, not a linked list)
Worst-case comparisons	n	⌊log₂ n⌋ + 1
n = 10⁶	1,000,000	20
Best case	1 (target first)	1 (target in the middle)
Works on	Any sequence, including streams	Sorted arrays, and any monotone predicate (see below)

Is sorting worth it? Sorting costs O(n log n) (next topic). If you will answer q queries, linear search costs about q·n in total, while sorting once and then using binary search costs about n log n + q log n. Sorting pays off as soon as q is more than about log n.

Variants. The most useful form of binary search returns a boundary, not a match. lower_bound(x) is the first position i with a[i] ≥ x, which is Python's bisect.bisect_left. It locates insertion points, counts occurrences (bisect_right(x) − bisect_left(x)) and answers range queries. More generally, binary search finds the first i at which any monotone yes/no predicate switches from false to true, for example "the first version that fails the test" in git bisect.

Lower bound. No comparison-based algorithm can search a sorted array in fewer than Ω(log n) comparisons in the worst case. Its decision tree (9.2) must have a separate leaf for each of the n positions, plus "absent", and a tree of small height has few leaves. Binary search is therefore optimal.

Key takeaways

• Linear search works on any data and costs n comparisons in the worst case.
• Binary search needs sorted, randomly accessible data and costs at most ⌊log₂ n⌋ + 1 comparisons, which is optimal for comparison-based search.
• Binary search is correct because of its invariant ("if x occurs, it is in a[lo:hi]") and terminates because hi − lo strictly decreases.
• The boundary form (lower_bound) generalizes to any monotone predicate.

Practice

1. (Beginner) Trace binary search on the list from the trace for x = 4 and for x = 5. How many comparisons does each search make, and what are lo and hi when the search for 5 fails?
2. (Intermediate) Modify binary search to return the first index of x in a sorted list that may contain duplicates, still in O(log n) time. State the new invariant, and use your function to count the occurrences of x in O(log n) time.
3. (Interview) A sorted array of distinct integers has been rotated at an unknown pivot, for example [15, 19, 22, 30, 1, 3, 4, 7, 9, 12]. Find a target in O(log n) time. Hint: for any mid, at least one of the halves a[lo..mid] and a[mid..hi−1] is sorted. Check whether the target lies within the range of the sorted half.

Sorting Algorithms

Why. Sorted data is easier to work with in almost every way. It allows binary search, puts duplicates next to each other, places the median in the middle, and lets two lists be merged or compared in a single pass. Sorting is also the classic laboratory for algorithm design: the same problem is solved by incremental, divide-and-conquer and randomized methods, at very different costs.

What. The sorting problem: given a₁, …, aₙ from a totally ordered set (2.5), output a permutation of them in nondecreasing order. Two further properties matter in practice:

• A sort is stable if elements with equal keys keep their original relative order. If you sort employees by name and then stably by department, each department stays sorted by name.
• A sort is in place if it uses only O(1) extra memory (or O(log n) for a recursion stack), beyond the array itself.

The main algorithms.

• Bubble sort. Sweep the array and swap every adjacent pair that is out of order. After sweep k, the k largest elements are in their final positions. Each swap removes exactly one inversion.
• Selection sort. Find the minimum of the unsorted part and swap it to the front of that part. It always makes n(n − 1)/2 comparisons, but only n − 1 swaps.
• Insertion sort. Insert each element into the sorted prefix to its left (invariant in 3.3). It makes one shift per inversion, so it is very fast on nearly sorted input.
• Merge sort. Split the array in half, sort each half recursively, and merge the two sorted halves in linear time. T(n) = 2T(n/2) + Θ(n) = Θ(n log n) (6.2).
• Quicksort. Choose a pivot, partition the array into elements smaller than and larger than the pivot, and recurse on both parts. It takes Θ(n log n) on average and Θ(n²) in the worst case. Choosing the pivot at random gives O(n log n) expected time on every input (7.4).
• Heapsort. Arrange the array as a binary max-heap (a complete binary tree, 9.1, stored in the array), then repeatedly move the maximum to the end. It takes Θ(n log n) time, in place.

                 [38 27 43  3  9 82 10]
         split ╱                         ╲
        [38 27 43  3]                 [9 82 10]
         ╱        ╲                    ╱      ╲
     [38 27]    [43  3]            [9 82]    [10]
      ╱   ╲      ╱   ╲              ╱  ╲       │
   [38]  [27]  [43]  [3]          [9] [82]   [10]       one element: already sorted
      ╲   ╱      ╲   ╱              ╲  ╱       │
     [27 38]    [ 3 43]            [9 82]    [10]
         ╲        ╱                    ╲      ╱
        [ 3 27 38 43]                 [9 10 82]
         merge ╲                         ╱
                 [ 3  9 10 27 38 43 82]

The merge step walks along both sorted halves and repeatedly outputs the smaller front element. It makes at most n − 1 comparisons. The recursion has ⌈log₂ n⌉ levels, and each level does O(n) work in total.

import random

def insertion_sort(a):
    a, comparisons = list(a), 0
    for i in range(1, len(a)):
        key, j = a[i], i - 1
        while j >= 0:
            comparisons += 1
            if a[j] <= key:                    # <= rather than < keeps equal keys in order (stable)
                break
            a[j + 1] = a[j]                    # shift the larger element one place right
            j -= 1
        a[j + 1] = key
    return a, comparisons

def merge_sort(a):
    if len(a) <= 1:
        return list(a), 0
    mid = len(a) // 2
    left, c1 = merge_sort(a[:mid])
    right, c2 = merge_sort(a[mid:])
    merged, i, j, comparisons = [], 0, 0, c1 + c2
    while i < len(left) and j < len(right):    # repeatedly take the smaller front element
        comparisons += 1
        if left[i] <= right[j]:                # <= takes from the left on ties: stable
            merged.append(left[i]); i += 1
        else:
            merged.append(right[j]); j += 1
    merged += left[i:] + right[j:]             # one side is used up; append the rest of the other
    return merged, comparisons

random.seed(1)
data = random.sample(range(1000), 1000)        # a random permutation of 0 … 999
for name, inp in [("random", data), ("sorted", sorted(data)), ("reversed", sorted(data)[::-1])]:
    print(f"{name:9} insertion: {insertion_sort(inp)[1]:>7}   merge: {merge_sort(inp)[1]:>5}")
# random    insertion:  251387   merge:  8705
# sorted    insertion:     999   merge:  4932
# reversed  insertion:  499500   merge:  5044

Insertion sort ranges from n − 1 = 999 comparisons to n(n − 1)/2 = 499,500, depending on the input. Merge sort stays below n log₂ n ≈ 9,966 on every input. The decision-tree lower bound (9.2) for n = 1000 is ⌈log₂ 1000!⌉ = 8,530 comparisons.

Algorithm	Best	Average	Worst	Extra space	Stable	Typical use
Bubble sort (with early exit)	Θ(n)	Θ(n²)	Θ(n²)	O(1)	Yes	Teaching
Selection sort	Θ(n²)	Θ(n²)	Θ(n²)	O(1)	No	When writes are expensive (n − 1 swaps)
Insertion sort	Θ(n)	Θ(n²)	Θ(n²)	O(1)	Yes	Small or nearly sorted arrays
Merge sort	Θ(n log n)	Θ(n log n)	Θ(n log n)	Θ(n)	Yes	Linked lists, external sorting, stable sorting
Quicksort	Θ(n log n)	Θ(n log n)	Θ(n²)	O(log n) stack	No	Fastest general-purpose in-memory sort
Heapsort	Θ(n log n)	Θ(n log n)	Θ(n log n)	O(1)	No	Guaranteed bound, in place
Counting sort	Θ(n + k)	Θ(n + k)	Θ(n + k)	Θ(n + k)	Yes	Integer keys in 0 … k − 1

The symbols Θ and O are defined precisely in 10.2. For now, read Θ(n²) as "proportional to n²".

The Ω(n log n) barrier. Every comparison sort needs ⌈log₂ n!⌉ = Ω(n log n) comparisons in the worst case (decision trees, 9.2), so merge sort and heapsort are asymptotically optimal. Counting sort and radix sort get around the barrier because they never compare keys: they use the keys as array indexes, which works only when the keys are small integers or fixed-length strings.

In real libraries. Python's sorted and Java's object sort use Timsort, a stable hybrid of merge sort and insertion sort that takes Θ(n) time on already-sorted runs. C++'s std::sort uses introsort: quicksort that falls back to heapsort if the recursion gets too deep, and to insertion sort for small subarrays.

Key takeaways

• Simple sorts (bubble, selection, insertion) take Θ(n²) time. Insertion sort takes Θ(n + I), where I is the number of inversions, so it is excellent on nearly sorted data.
• Merge sort and heapsort take Θ(n log n) in the worst case. Quicksort takes Θ(n log n) on average and Θ(n²) in the worst case.
• Ω(n log n) comparisons are necessary for any comparison sort. Non-comparison sorts avoid this bound by exploiting the structure of the keys.
• Stability and extra space are often what decides between algorithms with the same asymptotic time.

Practice

1. (Beginner) Run bubble sort on [5, 1, 4, 2, 8], showing the array after each sweep. Count the swaps and compare the count with the number of inversions in the original array.
2. (Intermediate) Prove that insertion sort performs exactly I shifts, where I is the number of inversions of the input, and between I and I + n − 1 comparisons. Conclude that it runs in Θ(n) time on any input with O(n) inversions.
3. (Interview) Sort an array containing only the values 0, 1 and 2 in a single pass, using O(1) extra space (the "Dutch national flag" problem). Hint: keep three pointers low, mid, high, with the invariant that a[0:low] holds 0s, a[low:mid] holds 1s, and a[high+1:] holds 2s. Decide what each of the three values at a[mid] does to the pointers.

Greedy Algorithms

Why. Many optimization problems ask for the best of exponentially many candidate solutions: the most meetings in one room, the fewest coins that make an amount, the cheapest network that connects every office. A greedy algorithm builds a solution one piece at a time. At each step it takes the choice that looks best right now, and it never reconsiders. When this works, the algorithm is short and fast. The hard part is knowing when it works, because a greedy algorithm that is not proved correct is only a heuristic.

What. A greedy algorithm has a selection rule (which candidate to consider next) and a feasibility check (whether that candidate can be added to the partial solution). Two properties make the greedy approach correct:

• Greedy-choice property: some optimal solution contains the first greedy choice.
• Optimal substructure: after that choice is made, what remains is a smaller instance of the same problem, and an optimal solution for it, combined with the choice, is optimal overall.

Greedy correctness is usually proved in one of two ways:

Technique	Idea	Used for
Greedy stays ahead	Show by induction that after each step, the greedy partial solution is at least as good as the corresponding part of any optimal solution	Interval scheduling (below), Dijkstra's algorithm (8.4)
Exchange argument	Take any optimal solution and swap its parts, one at a time, for greedy choices without making it worse	MST cut property (9.4), Huffman coding (9.2)

Example 1: interval scheduling. Given talks with start and finish times, schedule as many non-overlapping talks as possible in one room. Several natural greedy rules fail:

  earliest start first:   [================================]         greedy picks 1
                            [====]   [====]   [====]                 optimal is 3

  shortest first:         [==========]    [==========]               optimal is 2
                                    [======]                         greedy picks 1 (it blocks both)

The rule that works is earliest finish time first: choose the talk that ends first, discard every talk that overlaps it, and repeat. Finishing as early as possible leaves the most room for everything else.

Proof (greedy stays ahead). Let greedy choose g₁, …, g_k and let an optimal schedule be o₁, …, o_m, both sorted by finish time f. Claim: f(g_r) ≤ f(o_r) for every r ≤ k. For r = 1, this holds because g₁ has the earliest finish time of all talks. If f(g_{r−1}) ≤ f(o_{r−1}), then o_r starts after o_{r−1} ends, so after g_{r−1} ends, and it was still available when greedy made its r-th choice. Greedy chose the available talk that finishes first, so f(g_r) ≤ f(o_r). Finally, if m > k, then o_{k+1} starts after f(o_k) ≥ f(g_k), so it was still available and greedy would not have stopped. Therefore k = m. ∎

def schedule(talks):
    chosen, last_end = [], float("-inf")
    for start, end in sorted(talks, key=lambda t: t[1]):   # earliest finish time first: O(n log n)
        if start >= last_end:                              # compatible with every talk chosen so far
            chosen.append((start, end))
            last_end = end
    return chosen

talks = [(1, 4), (3, 5), (0, 6), (5, 7), (3, 9), (5, 9),
         (6, 10), (8, 11), (8, 12), (2, 14), (12, 16)]
print(schedule(talks))                                     # [(1, 4), (5, 7), (8, 11), (12, 16)]

Example 2: making change. The cashier's algorithm repeatedly takes the largest coin that fits. With the coins 25, 10, 5 and 1 it always uses the fewest coins. With other coin systems it can fail, which is the counterexample asked for in 1.4. The check below compares it with an exact dynamic-programming solution (compare the coin-change counting table in 5.6):

def greedy_change(coins, amount):
    used = []
    for c in sorted(coins, reverse=True):                  # largest denomination first
        k, amount = divmod(amount, c)                      # take as many of c as fit
        used += [c] * k
    return used if amount == 0 else None

def fewest_coins(coins, amount):
    best = [0] + [float("inf")] * amount                   # best[t] = fewest coins that make t
    for t in range(1, amount + 1):
        best[t] = min((best[t - c] + 1 for c in coins if c <= t), default=float("inf"))
    return best[amount]

print(greedy_change([25, 10, 5, 1], 68), fewest_coins([25, 10, 5, 1], 68))
# [25, 25, 10, 5, 1, 1, 1] 7          greedy is optimal for these coins
print(greedy_change([25, 10, 1], 30), fewest_coins([25, 10, 1], 30))
# [25, 1, 1, 1, 1, 1] 3                greedy uses 6 coins, but 10 + 10 + 10 uses 3

Greedy algorithms in this document.

Problem	Greedy rule	Optimal?
Interval scheduling	Earliest finish time	Yes (stays ahead)
Shortest paths, nonnegative weights (8.4)	Settle the closest unsettled vertex	Yes (stays ahead)
Minimum spanning tree (9.4)	Prim: lightest edge leaving the tree. Kruskal: lightest edge that closes no cycle	Yes (exchange, cut property)
Optimal prefix code (9.2)	Huffman: merge the two least frequent symbols	Yes (exchange)
Fractional knapsack	Highest value-to-weight ratio first	Yes (exchange)
0/1 knapsack	Highest ratio first	No: use dynamic programming
Change with arbitrary coins	Largest coin first	No: use dynamic programming
Graph coloring (8.5)	Smallest color not used by a neighbor	No: at most Δ + 1 colors, possibly far more than χ(G)
Traveling salesperson (8.4)	Nearest unvisited city	No: can be far from optimal

Analogy. A greedy hiker always walks uphill along the steepest direction. On a single smooth hill this reaches the summit. On a mountain range it can get stuck on a minor peak. A greedy algorithm is correct exactly when the problem is "a single hill", and the proof techniques above are how you show that it is.

Key takeaways

• A greedy algorithm makes the locally best choice at each step and never undoes it.
• It is correct only if the problem has the greedy-choice property and optimal substructure. Prove this by "greedy stays ahead" or by an exchange argument.
• For interval scheduling, the right rule is earliest finish time. Earliest start and shortest duration fail.
• When greedy fails (0/1 knapsack, arbitrary coin systems), dynamic programming is usually the exact alternative.

Practice

1. (Beginner) With coins 1, 5, 10, 20 and 25, what does the cashier's algorithm give for 40? Find a solution with fewer coins.
2. (Intermediate) In the fractional knapsack problem you may take any fraction of each item. Prove, with an exchange argument, that taking items in decreasing order of value-to-weight ratio is optimal. Then give a three-item instance of the 0/1 knapsack problem (whole items only) where the same rule is not optimal.
3. (Interview) Given a list of meeting intervals, find the minimum number of rooms needed so that no two overlapping meetings share a room. Hint: process meetings by start time and keep a min-heap of the end times of the rooms in use. Reuse a room if its earliest end time is at most the new start time. Show that the answer equals the largest number of meetings in progress at any single moment, which is a lower bound that the greedy algorithm meets.

<a id="102-growth-of-functions"></a>

10.2 Growth of Functions

This subchapter introduces the asymptotic notation that compares functions by how fast they grow for large inputs, ignoring constant factors and small cases. It then catalogs the growth rates that appear in practice and gives techniques for comparing unfamiliar ones.

Big-O Notation

Why. The exact number of steps an algorithm takes depends on the machine, the compiler, and even on what you count as a step: is a[i] > a[best] one operation or three? None of this changes the question that matters, which is how the cost scales. If the input doubles, does the time double, quadruple, or square? Big-O notation answers that question by ignoring constant factors and small inputs, so its statements hold on every machine. It plays the role of "about a million people" for the size of a city: an order of magnitude, not a head count.

What. Let f and g be functions from the natural numbers (or the reals) to the reals. We say f(n) is O(g(n)) if there are constants C > 0 and k such that

  |f(n)| ≤ C·|g(n)|      for all n > k.

The constants C and k are called witnesses. In words: from some point on, f is bounded by a constant multiple of g. Big-O is an upper bound on growth.

  cost
   │                                      ╱  C·g(n)
   │                                   ╱
   │                                ╱
   │                             ╱
   │   · · · · · · · · · · · ·╳· · · · · · · · · · f(n)
   │                       ╱
   │                    ╱
   │                 ╱
   │              ╱
   └──────────────────────────┼───────────────────────── n
                              k
       f(n) > C·g(n) allowed  │ f(n) ≤ C·g(n) for all n > k

Example proof. f(n) = 7n² + 3n + 5 is O(n²). For n > 1 we have 3n ≤ 3n² and 5 ≤ 5n², so

  7n² + 3n + 5  ≤  7n² + 3n² + 5n²  =  15n²       for n > 1.

The witnesses C = 15, k = 1 work. Witnesses are never unique: C = 8 also works, but needs n² ≥ 3n + 5, which holds for n ≥ 5, so k = 4.

Non-example. n² is not O(n). Suppose n² ≤ C·n for all n > k. Dividing by n gives n ≤ C for all n > k, which is false for n = max(k, C) + 1. No witnesses exist.

Rules. These make most proofs one line long:

Rule	Statement
Constant factors	c·f(n) is O(f(n)) for any constant c
Polynomials	a_d·nᵈ + … + a₁·n + a₀ is O(nᵈ). For n > 1 it is at most `(
Sum	If f₁ is O(g₁) and f₂ is O(g₂), then f₁ + f₂ is `O(max(
Product	If f₁ is O(g₁) and f₂ is O(g₂), then f₁·f₂ is O(g₁·g₂)
Transitivity	If f is O(g) and g is O(h), then f is O(h)
Logarithms	log_a n is O(log_b n) for any bases a, b > 1, since log_a n = log_b n / log_b a

For example, log₂(n!) ≤ log₂(nⁿ) = n·log₂ n, so log(n!) is O(n log n). And 1 + 2 + … + n = n(n + 1)/2 is O(n²) by the polynomial rule.

Notation warnings.

• "f(n) = O(g(n))" is the common way to write this, but the = is one-way. n = O(n²) and n² = O(n²) do not imply n = n². It is safest to think of O(g) as a set of functions and to read the statement as f ∈ O(g).
• Big-O is only an upper bound, so "binary search runs in O(n³) time" is true but useless. Give the smallest bound you can justify, and use Θ (below) when the bound is tight.

f = lambda n: 7 * n**2 + 3 * n + 5
g = lambda n: n**2

def witnesses_hold(C, k, upto=10**5):     # a finite check: evidence, never a proof
    return all(f(n) <= C * g(n) for n in range(k + 1, upto))

print(witnesses_hold(15, 1))              # True
print(witnesses_hold(8, 4))               # True
print(witnesses_hold(8, 3))               # False: n = 4 gives 129 > 128
print(witnesses_hold(7, 1000))            # False: 7n² + 3n + 5 > 7n² for every n, so C = 7 never works

Key takeaways

• f is O(g) when |f(n)| ≤ C·|g(n)| for all n > k, for some witnesses C and k.
• To prove a big-O bound, exhibit witnesses. To disprove one, show that no constant C can work.
• Constant factors and lower-order terms vanish: a polynomial of degree d is O(nᵈ), and the base of a logarithm does not matter.
• Big-O is an upper bound only. f(n) = O(g(n)) means f ∈ O(g), not equality.

Practice

1. (Beginner) Find witnesses C and k showing that 3n³ + 2n − 7 is O(n³), and that (n + 1)² is O(n²).
2. (Intermediate) Prove that 2ⁿ⁺¹ is O(2ⁿ) but 2²ⁿ is not O(2ⁿ). Is log₂ n O(log₁₀ n)? Is n^{log₂ 3} O(n²)?
3. (Interview) A colleague says: "Algorithm A is O(n²) and algorithm B is O(n log n), so B is always faster." Explain everything that is wrong with this claim. Hint: big-O is only an upper bound (A might actually be linear), it hides constant factors, and it says nothing about the input sizes you actually have.

Big-Omega Notation

Why. Big-O says "no worse than". Many important statements are the opposite kind: "this algorithm takes at least quadratic time on some inputs", "every comparison sort needs at least n log n comparisons" (9.2), "any algorithm must at least read its input". These are lower bounds, and they need their own notation.

What. We say f(n) is Ω(g(n)) if there are constants C > 0 and k such that

  |f(n)| ≥ C·|g(n)|      for all n > k.

Big-Omega is the mirror image of big-O:

  f is Ω(g)   ⟺   g is O(f)          (use the witnesses 1/C and k)

Examples.

• 7n² + 3n + 5 is Ω(n²): it is at least 7n² for every n ≥ 0, so C = 7, k = 0 work.
• n(n − 1)/2 is Ω(n²): for n ≥ 2 we have n − 1 ≥ n/2, so n(n − 1)/2 ≥ n²/4. Witnesses C = 1/4, k = 1.
• log₂(n!) is Ω(n log n): the largest n/2 factors of n! are each at least n/2, so n! ≥ (n/2)^{n/2} and

  log₂(n!)  ≥  (n/2)·log₂(n/2)  =  (n/2)·(log₂ n − 1)  ≥  (n/4)·log₂ n      for n ≥ 4,

since log₂ n − 1 ≥ (log₂ n)/2 exactly when n ≥ 4. Combined with the upper bound in Big-O Notation, this is what makes the sorting lower bound ⌈log₂ n!⌉ equal to Ω(n log n).

• √n is not Ω(n): √n ≥ C·n means n ≤ 1/C², which fails for large n.

Two different uses of Ω. It is important not to confuse a lower bound on one algorithm with a lower bound on a problem:

Statement	Meaning	How it is proved
The worst-case time of algorithm A is O(g)	A never takes more than about g(n) steps	Bound the cost of every input of size n
The worst-case time of algorithm A is Ω(g)	Some inputs force A to take at least about g(n) steps	Exhibit one bad input of each size
Problem P has a lower bound of Ω(g)	Every algorithm for P needs Ω(g(n)) steps in the worst case	Decision trees (9.2), adversary arguments, counting

The third kind is much harder to prove, because it is a statement about all algorithms, including ones nobody has invented yet.

A common confusion. Ω does not mean "best case", and O does not mean "worst case". O, Ω and Θ describe the growth of a function. Best, worst and average case (10.3) choose which function you describe. "The best case of insertion sort is O(n)" and "the worst case of insertion sort is Ω(n²)" are both correct and meaningful.

from math import lgamma, log, log2

def log2_factorial(n):                      # log₂(n!) via the log-gamma function: lgamma(n + 1) = ln(n!)
    return lgamma(n + 1) / log(2)

for n in (4, 10, 100, 10**4, 10**6):
    lower = (n / 4) * log2(n)               # the Ω witness bound proved above
    print(f"n={n:>7}  log2(n!)={log2_factorial(n):14.1f}  (n/4)log2 n={lower:12.1f}"
          f"  ratio to n·log2 n={log2_factorial(n) / (n * log2(n)):.3f}")
# n=      4  log2(n!)=           4.6  (n/4)log2 n=         2.0  ratio to n·log2 n=0.573
# n=     10  log2(n!)=          21.8  (n/4)log2 n=         8.3  ratio to n·log2 n=0.656
# n=    100  log2(n!)=         524.8  (n/4)log2 n=       166.1  ratio to n·log2 n=0.790
# n=  10000  log2(n!)=      118458.1  (n/4)log2 n=     33219.3  ratio to n·log2 n=0.891
# n=1000000  log2(n!)=    18488884.8  (n/4)log2 n=   4982892.1  ratio to n·log2 n=0.928

The ratio creeps slowly toward 1, because log₂(n!) = n·log₂ n − n·log₂ e + O(log n) by Stirling's formula.

Key takeaways

• f is Ω(g) when |f(n)| ≥ C·|g(n)| for all n > k. Equivalently, g is O(f).
• Ω expresses lower bounds: on the cost of an algorithm, or on every algorithm for a problem.
• A lower bound for a problem, such as Ω(n log n) for comparison sorting, rules out all algorithms, so it needs a special argument.
• Asymptotic notation and best/worst/average case are independent ideas. Do not treat Ω as a synonym for "best case".

Practice

1. (Beginner) Find witnesses showing that n³ − 100n² is Ω(n³).
2. (Intermediate) Prove that f is O(g) if and only if g is Ω(f). Use this to show that n log n is Ω(n) but not O(n).
3. (Interview) Prove that any algorithm that decides whether an unsorted array of n integers contains x must, in the worst case, read all n positions. Hint: use an adversary argument. If an algorithm answers without reading position i, the adversary can place x at position i, or not, without changing anything the algorithm saw, so one of the two answers is wrong.

Big-Theta Notation

Why. Upper bounds can be loose: "merge sort is O(n³)" is true. To say what the growth rate is, you need an upper and a lower bound of the same order. That is Θ. When people say "merge sort is O(n log n)", they almost always mean Θ(n log n).

What. We say f(n) is Θ(g(n)) if f is both O(g) and Ω(g). Equivalently, there are constants C₁, C₂ > 0 and k such that

  C₁·|g(n)|  ≤  |f(n)|  ≤  C₂·|g(n)|      for all n > k.

Then f and g are of the same order. Θ is an equivalence relation (2.5): it is reflexive, symmetric and transitive. Its equivalence classes are the growth rates.

The five symbols as comparisons. Comparing growth rates works like comparing numbers:

Notation	Analogy	Meaning (for positive f and g)
f is O(g)	f ≤ g	f grows no faster than g
f is Ω(g)	f ≥ g	f grows at least as fast as g
f is Θ(g)	f = g	Same growth rate
f is o(g)	f < g	f(n)/g(n) → 0: f grows strictly slower
f is ω(g)	f > g	f(n)/g(n) → ∞: f grows strictly faster

Limit test. If L = lim_{n→∞} f(n)/g(n) exists, with f and g positive, then:

• 0 < L < ∞ implies that f is Θ(g).
• L = 0 implies that f is O(g) but not Ω(g), that is, f is o(g).
• L = ∞ implies that f is Ω(g) but not O(g), that is, f is ω(g).

The test only applies when the limit exists. f(n) = n·(2 + (−1)ⁿ) is Θ(n) with witnesses C₁ = 1 and C₂ = 3, although f(n)/n alternates between 1 and 3 and never converges.

Standard Θ facts.

Function	Order	Reason
a_d·nᵈ + … + a₀ with a_d > 0	Θ(nᵈ)	The ratio to nᵈ tends to a_d
1ᵏ + 2ᵏ + … + nᵏ (k ≥ 0)	Θ(nᵏ⁺¹)	At most n·nᵏ. The top half alone is at least (n/2)·(n/2)ᵏ
log(n!)	Θ(n log n)	The O and Ω proofs above
H_n = 1 + 1/2 + … + 1/n	Θ(log n)	H_n ≈ ln n + 0.5772 (3.1)
log_a n for any base a > 1	Θ(log n)	Bases differ by a constant factor, so we write log n with no base
aⁿ versus bⁿ for 1 < a < b	Not Θ	(a/b)ⁿ → 0: unlike the base of a logarithm, the base of an exponential matters

Proof that 3n² − 10n + 7 is Θ(n²). Upper bound: 3n² − 10n + 7 ≤ 3n² + 7n² = 10n² for n ≥ 1. Lower bound: 3n² − 10n + 7 ≥ 2n² exactly when n² − 10n + 7 ≥ 0, which holds for n ≥ 10. So C₁ = 2, C₂ = 10, k = 9. ∎

from math import log, log2

pairs = [
    ("3n² + 10n log n  vs  n²", lambda n: 3 * n**2 + 10 * n * log2(n), lambda n: n**2),
    ("n log n  vs  n^1.5",      lambda n: n * log2(n),                 lambda n: n**1.5),
    ("H_n  vs  ln n",           lambda n: sum(1 / i for i in range(1, n + 1)), lambda n: log(n)),
]
for name, f, g in pairs:                                     # ratios f(n)/g(n) for growing n
    print(f"{name:26}", "  ".join(f"{f(n) / g(n):7.3f}" for n in (10, 10**3, 10**5, 10**7)))
# 3n² + 10n log n  vs  n²      6.322    3.100    3.002    3.000      → 3: Θ
# n log n  vs  n^1.5           1.050    0.315    0.053    0.007      → 0: o, so O but not Θ
# H_n  vs  ln n                1.272    1.084    1.050    1.036      → 1: Θ, but very slowly

Key takeaways

• f is Θ(g) when it is both O(g) and Ω(g): sandwiched between two constant multiples of g from some point on.
• When f(n)/g(n) tends to a positive finite limit, f is Θ(g). A limit of 0 or ∞ rules out Θ.
• A polynomial of degree d with positive leading coefficient is Θ(nᵈ), Σ iᵏ is Θ(nᵏ⁺¹), and log(n!) is Θ(n log n).
• The base of a logarithm does not matter inside Θ. The base of an exponential does.

Practice

1. (Beginner) Show with explicit witnesses C₁, C₂, k that (n + 5)³ is Θ(n³).
2. (Intermediate) Prove that Σ_{i=1}^{n} log i is Θ(n log n) without Stirling's formula, and that ⌈n/2⌉·⌊n/2⌋ is Θ(n²).
3. (Interview) You tell an interviewer that your solution is O(n²). They ask: "Is that bound tight?" What are they asking, and how do you answer convincingly? Hint: they want to know whether the worst case is Θ(n²). Show a family of inputs on which your algorithm really performs Ω(n²) steps, or tighten the upper bound.

Common Growth Rates

Why. Most algorithms fall into a handful of growth classes. If you recognize them, and know roughly how large an input each class can handle, you can choose an approach before writing any code. A useful rule of thumb is that a modern machine performs on the order of 10⁸ simple operations per second.

What. The standard classes, from slowest-growing to fastest-growing:

Growth	Name	Typical algorithm
1	Constant	Array indexing, hash-table lookup (expected), push and pop on a stack
log n	Logarithmic	Binary search, an operation on a balanced search tree (9.2)
√n	Square root	Trial-division primality test (4.1)
n	Linear	Linear search, finding the maximum, BFS and DFS (n + m, 8.4)
n log n	Linearithmic	Merge sort, heapsort, Kruskal's algorithm (9.4)
n²	Quadratic	Insertion sort, checking all pairs
n³	Cubic	Naive matrix multiplication, Floyd–Warshall all-pairs shortest paths (8.4)
2ⁿ	Exponential	Trying all subsets, brute-force SAT (1.1)
n!	Factorial	Trying all permutations, brute-force TSP (8.4)

What each class means in seconds. The time for f(n) operations at 10⁸ operations per second:

f(n)	n = 10	n = 20	n = 50	n = 1,000	n = 10⁶
log₂ n	instant	instant	instant	instant	instant
n	instant	instant	instant	instant	0.01 s
n log₂ n	instant	instant	instant	0.1 ms	0.2 s
n²	instant	instant	instant	0.01 s	2.8 hours
n³	instant	0.1 ms	1.3 ms	10 s	317 years
2ⁿ	instant	0.01 s	130 days	about 10²⁸⁵ years	—
n!	0.04 s	771 years	about 10⁴⁹ years	—	—

Polynomial classes degrade gracefully. Exponential and factorial classes go from instant to hopeless within a few dozen elements.

Faster hardware does not rescue exponential algorithms. The largest n that fits in a budget of 10⁸ operations, and in a budget 1000 times larger:

from math import factorial, log2

rates = {
    "n":       lambda n: n,
    "n log n": lambda n: n * log2(n),
    "n²":      lambda n: n**2,
    "n³":      lambda n: n**3,
    "2ⁿ":      lambda n: 2**n,
    "n!":      lambda n: factorial(n),
}

def largest_n(f, budget):                     # largest n with f(n) <= budget, for increasing f
    lo, hi = 1, 2
    while f(hi) <= budget:                    # double hi until it exceeds the budget
        lo, hi = hi, 2 * hi
    while hi - lo > 1:                        # binary search (10.1) on the boundary
        mid = (lo + hi) // 2
        lo, hi = (mid, hi) if f(mid) <= budget else (lo, mid)
    return lo

for name, f in rates.items():
    print(f"{name:8} {largest_n(f, 10**8):>12,} {largest_n(f, 10**11):>16,}")
# n         100,000,000  100,000,000,000
# n log n     4,523,071    3,168,454,160
# n²             10,000          316,227
# n³                464            4,641
# 2ⁿ                 26               36
# n!                 11               14

A machine 1000 times faster multiplies the feasible n by 1000 for linear time, by about 32 for quadratic time and by 10 for cubic time, but it adds only 10 for 2ⁿ (because 2¹⁰ ≈ 1000) and 3 for n!.

The hierarchy. Each function below is o of the next one:

  1 ≺ log log n ≺ log n ≺ (log n)² ≺ √n ≺ n ≺ n log n ≺ n² ≺ n³ ≺ 2ⁿ ≺ 3ⁿ ≺ n! ≺ nⁿ

Three facts generate most of it. For all constants a, b > 0 and c > 1:

• Logarithms lose to powers: (log n)ᵃ is o(nᵇ). Even (log n)¹⁰⁰ is eventually smaller than n^{0.01}.
• Powers lose to exponentials: nᵃ is o(cⁿ). Even n¹⁰⁰ is eventually smaller than 1.01ⁿ.
• Exponentials lose to factorials: cⁿ is o(n!), and n! is o(nⁿ).

Key takeaways

• The common classes are 1 ≺ log n ≺ n ≺ n log n ≺ n² ≺ n³ ≺ 2ⁿ ≺ n!.
• At 10⁸ operations per second: n log n handles millions of elements, n² about ten thousand, n³ a few hundred, 2ⁿ a few dozen, and n! about a dozen.
• Faster hardware multiplies the feasible input size of a polynomial algorithm, but only adds a constant to that of an exponential one.
• Logarithms lose to powers, powers lose to exponentials, and exponentials lose to factorials.

Practice

1. (Beginner) Arrange in increasing order of growth: n^{1.5}, log₂(n²), 2^{log₂ n}, n!, n·log n, 1.5ⁿ, 100, n²/log n.
2. (Intermediate) An algorithm takes 1 second on an input of size 1000. Estimate its running time on inputs of size 2000 and 10,000 if its running time is Θ(n), Θ(n log n), Θ(n²), and Θ(2ⁿ).
3. (Interview) A problem statement says n ≤ 10⁵. Which running times are acceptable for a one-second limit, and what would n ≤ 20 or n ≤ 500 suggest? Hint: use the 10⁸ rule of thumb. n² = 10¹⁰ is too slow, while n log n ≈ 1.7 × 10⁶ is fine. Small limits are often a clue: n ≤ 20 invites 2ⁿ (subsets), and n ≤ 500 invites n³.

Comparing Function Growth

Why. Real running times do not always come in textbook form. Expressions such as n^{log n}, 2^{√n}, (log n)^{log n} and n/log n appear in the analysis of real algorithms, and you need reliable techniques to place them in the hierarchy.

What. Four techniques, from simplest to most powerful:

1. Simplify first. Drop constant factors and lower-order terms (the sum rule): 5n³ + n² log n becomes n³.
2. Take the ratio f(n)/g(n) and find its limit (the limit test). For continuous extensions, L'Hôpital's rule often helps: lim (ln n)/n = lim (1/n)/1 = 0.
3. Compare logarithms. If log f(n) − log g(n) → −∞, then f(n)/g(n) → 0, so f is o(g). This tames exponentials and towers of powers.
4. Substitute. Writing n = 2ᵐ turns log n into m, which often makes the comparison obvious.

Worked comparisons.

Compare	Technique	Result
n^{log₂ n} vs 2ⁿ	Logarithms: (log₂ n)² vs n	(log n)² ≺ n, so n^{log n} ≺ 2ⁿ. It is superpolynomial (it beats every nᵏ) but subexponential
2^{√n} vs n¹⁰	Logarithms: √n vs 10·log₂ n	√n wins, so 2^{√n} eventually beats every polynomial
(log n)^{log n} vs n²	Substitute n = 2ᵐ: mᵐ vs 4ᵐ	mᵐ ≻ 4ᵐ, so (log n)^{log n} is superpolynomial
n / log n vs √n	Ratio: √n / log n → ∞	n / log n ≻ √n
3ⁿ vs 2ⁿ	Ratio: (3/2)ⁿ → ∞	3ⁿ ≻ 2ⁿ: they are not Θ of each other
2ⁿ⁺¹ vs 2ⁿ	Ratio: exactly 2	Θ: a constant added in the exponent is a constant factor
2²ⁿ vs 2ⁿ	Ratio: 2ⁿ → ∞	4ⁿ ≻ 2ⁿ: a constant multiplying the exponent changes the base

A logarithm trap. Comparing logarithms by their difference is safe. Comparing them by their ratio is not. log(n²) = 2·log n is Θ(log n), yet n² is not Θ(n). In the same way, log(n!) and log(nⁿ) are both Θ(n log n), yet n! = o(nⁿ). Taking logarithms can hide polynomial and even exponential factors.

Asymptotics say "eventually", not "now". An asymptotically better function can be worse for every input you will ever see:

from math import log2

def first_overtake(log_f, log_g, start=2):
    """Smallest n >= start with g(n) > f(n). Compares log₂ values, so huge numbers never appear."""
    n = start
    while log_g(n) <= log_f(n):
        n += 1
    return n

print(first_overtake(lambda n: log2(100 * n), lambda n: 2 * log2(n)))      # 101    n² passes 100n
print(first_overtake(lambda n: 10 * log2(n), lambda n: n))                # 59     2ⁿ passes n¹⁰
print(first_overtake(lambda n: 2 * log2(n), lambda n: n * log2(1.01)))    # 1466   1.01ⁿ passes n²
# n^1.1 vs n·log₂ n: substitute n = 2^m, which compares 2^(0.1·m) with m
print(first_overtake(lambda m: log2(m), lambda m: 0.1 * m))               # 59     so n ≈ 2⁵⁹ ≈ 5.8 × 10¹⁷

n^{1.1} is asymptotically larger than n log₂ n, but it only overtakes it at an input size of about 5.8 × 10¹⁷, far beyond any real array. When constants or crossover points are this extreme, measure instead of relying on the asymptotic ordering. This is why library sorts switch to insertion sort for small subarrays.

Key takeaways

• Simplify, then compare by the ratio limit, by the difference of logarithms, or by substituting n = 2ᵐ.
• n^{log n} and 2^{√n} lie strictly between polynomial and exponential growth.
• Constants inside an exponent matter: 2ⁿ⁺¹ is Θ(2ⁿ), but 2²ⁿ is not.
• log f = Θ(log g) does not imply f = Θ(g).
• Asymptotic order describes large n. Crossover points can be enormous, so small-input performance needs measurement.

Practice

1. (Beginner) For each pair, decide whether f is O(g), Ω(g), or both: (a) log(n³) and log n; (b) 2ⁿ and 2^{n/2}; (c) n^{√n} and 2ⁿ; (d) n·2ⁿ and 3ⁿ.
2. (Intermediate) Prove that if f is O(g), with f(n) ≥ 1 and g(n) ≥ 2 for large n, then log f is O(log g). Give an example showing that the converse fails.
3. (Interview) Algorithm A costs 50·n·log₂ n operations and algorithm B costs n². For which n is A cheaper? How would you use the answer to build a hybrid sort, and why do production sorts actually choose their cutoff by measurement? Hint: solve 50·log₂ n < n numerically. Real constants depend on caches and branch prediction, which no operation count captures.

<a id="103-complexity-analysis"></a>

10.3 Complexity Analysis

This subchapter applies asymptotic notation to measure the time and memory an algorithm uses, and distinguishes the cases over which those measurements are taken. It then classifies problems themselves, from tractable ones to the NP-complete problems for which no efficient algorithm is known.

Time Complexity

Why. Wall-clock time depends on the processor, the language, the cache, and whatever else the machine is doing. To compare algorithms on paper, we count the basic operations they perform, as a function of the input size, and summarize that count with Θ. The hidden constant absorbs the machine. What remains is the scaling behavior, and that is a property of the algorithm alone. Think of it as fuel consumption per kilometer rather than the time of one particular trip.

What. The time complexity of an algorithm is the number of basic operations (comparisons, arithmetic operations, assignments, array accesses) it performs, as a function of the input size n. We use the RAM model: every basic operation on a machine-word-sized number costs 1.

What counts as the input size depends on the problem:

Input	Size measure
Array or list	Number of elements n
Graph	Number of vertices n and edges m, written together as O(n + m)
A single integer N	Number of bits, b = ⌈log₂(N + 1)⌉, not the value N
String	Number of characters

Rules for analyzing code.

Construct	Cost
Sequence S₁; S₂	T₁ + T₂, which is Θ(max(T₁, T₂))
if c then S₁ else S₂	Cost of c plus max(T₁, T₂) (worst case)
Loop of k iterations	Sum of the costs of the iterations, which is k·T if each costs T
Nested loops	Nested sums, evaluated as in 3.1
Loop where i doubles or halves	Θ(log n) iterations
Recursion	A recurrence (6.1), often solved with the master theorem (6.2)

Example. Four loop patterns and their exact counts:

from math import log

def count_ops(n):
    pairs = sum(1 for i in range(n) for j in range(i + 1, n))    # Σ (n − 1 − i) = n(n − 1)/2: Θ(n²)

    doubling, i = 0, 1
    while i <= n:                                                 # i = 1, 2, 4, …: ⌊log₂ n⌋ + 1 passes: Θ(log n)
        doubling += 1
        i *= 2

    nested_log = 0
    for i in range(n):                                            # n passes of a Θ(log n) inner loop: Θ(n log n)
        j = 1
        while j < n:
            nested_log += 1
            j *= 2

    harmonic = sum(len(range(0, n, step)) for step in range(1, n + 1))   # Σ ⌈n/step⌉ ≈ n·H_n: Θ(n log n)
    return pairs, doubling, nested_log, harmonic

for n in (10, 100, 1000):
    p, d, nl, h = count_ops(n)
    print(f"n={n:>4}  pairs={p:>6}  doubling={d:>2}  nested={nl:>5}  harmonic={h:>5}  "
          f"harmonic/(n ln n)={h / (n * log(n)):.2f}")
# n=  10  pairs=    45  doubling= 4  nested=   40  harmonic=   33  harmonic/(n ln n)=1.43
# n= 100  pairs=  4950  doubling= 7  nested=  700  harmonic=  573  harmonic/(n ln n)=1.24
# n=1000  pairs=499500  doubling=10  nested=10000  harmonic= 8053  harmonic/(n ln n)=1.17

The last loop is the one that is easy to get wrong. Its inner loop shrinks as step grows, so the total is Σ ⌈n/step⌉, which lies between n·H_n and n·H_n + n, so it is Θ(n log n) (3.1). The ratio to n ln n approaches 1 only slowly, because H_n − ln n → 0.5772. It is not Θ(n²), as two nested loops might suggest. The same pattern appears when you loop over the multiples of every d ≤ n, for example to list the divisors of all numbers up to n. Restricting d to primes, as the sieve of Eratosthenes does (4.1), lowers the cost to Θ(n log log n).

Input size for numbers. Trial division tests N for primality with about √N divisions. That sounds fast, but the input is the b-bit representation of N, and √N = 2^{b/2}, which is exponential in b. For a 2048-bit RSA modulus (4.4) this is 2¹⁰²⁴ divisions. Algorithms that are polynomial in the value of a number but exponential in its length are called pseudo-polynomial.

Amortized cost. A Python list (a dynamic array) doubles its capacity when it is full and copies all its elements. A single append can therefore cost Θ(n). But over n appends the copies total at most 1 + 2 + 4 + … + 2^{⌊log₂ n⌋} < 2n, so the total cost is Θ(n) and the amortized cost per append is O(1). Amortization averages over a sequence of operations, not over random inputs, so it is a worst-case guarantee for the whole sequence.

Key takeaways

• Time complexity counts basic operations as a function of input size and is summarized with Θ or O.
• Sequences add, loops multiply or sum, loops that double or halve take Θ(log n) iterations, and recursion leads to recurrences.
• Measure the size of a number by its bits. An algorithm that takes Θ(√N) steps on the number N is exponential.
• Amortized analysis bounds the total cost of a sequence of operations. Dynamic-array append is O(1) amortized.

Practice

1. (Beginner) Give the Θ running time of each snippet: (a) for i in range(n): for j in range(i): x += 1; (b) i = n; while i > 1: i //= 3; (c) for i in range(n): for j in range(n): for k in range(10): x += 1.
2. (Intermediate) Use ln(n + 1) ≤ H_n ≤ 1 + ln n to prove that the harmonic loop above performs Θ(n log n) iterations. Then prove that a dynamic array that grows by a constant number of slots (instead of doubling) makes n appends cost Θ(n²) in total.
3. (Interview) Two sum. Given n integers and a target t, decide whether two of them add up to t. Give an O(n²) solution, an O(n log n) solution and an O(n) expected-time solution, and state the space used by each. Hint: check all pairs; sort, then move two pointers inward from the ends; scan once while storing the values seen so far in a hash set.

Space Complexity

Why. Memory is the other resource an algorithm consumes, and sometimes it is the scarcer one. Data may not fit in RAM, embedded devices and GPUs have small fixed memories, and deep recursion can overflow the call stack: Python allows only 1000 nested calls by default. Two algorithms with the same running time can differ enormously in memory.

What. The space complexity of an algorithm is the maximum amount of memory it uses at any one time, as a function of the input size. We usually count auxiliary space: memory beyond the input itself. Auxiliary space includes the recursion stack, which costs the maximum recursion depth times the size of a stack frame.

In the RAM model, an algorithm cannot use more memory cells than it has time to write, so its space is at most its time: S(n) = O(T(n)). The converse does not hold. An algorithm can run for a long time in very little memory, by reusing the same cells.

Examples.

Algorithm	Time	Auxiliary space	Where the space goes
Iterative sum, linear search	Θ(n)	Θ(1)	A few variables
Recursive sum	Θ(n)	Θ(n)	One stack frame per element
Binary search, iterative / recursive	Θ(log n)	Θ(1) / Θ(log n)	Recursion depth log n
Merge sort	Θ(n log n)	Θ(n)	Merge buffers, plus Θ(log n) stack
Quicksort	Θ(n log n) average	Θ(log n) if it recurses on the smaller part first	Stack only
Heapsort	Θ(n log n)	Θ(1)	In place
BFS / DFS (8.4)	Θ(n + m)	Θ(n)	Queue or stack, plus the visited set

import sys

def sum_recursive(a, i=0):                     # one stack frame per element: Θ(n) auxiliary space
    return 0 if i == len(a) else a[i] + sum_recursive(a, i + 1)

def sum_iterative(a):                          # one accumulator: Θ(1) auxiliary space
    total = 0
    for x in a:
        total += x
    return total

data = list(range(100_000))
print(sum_iterative(data))                     # 4999950000
print(sys.getrecursionlimit())                 # 1000
try:
    sum_recursive(data)
except RecursionError:
    print("RecursionError")                    # the stack, not the time, ran out

Time–space trade-offs. Extra memory can often buy time, and the reverse:

from functools import lru_cache

calls = 0
def fib_naive(n):                              # Θ(φⁿ) time, Θ(n) stack space
    global calls
    calls += 1
    return n if n < 2 else fib_naive(n - 1) + fib_naive(n - 2)

@lru_cache(maxsize=None)
def fib_memo(n):                               # Θ(n) time, Θ(n) space: the cache plus the stack
    return n if n < 2 else fib_memo(n - 1) + fib_memo(n - 2)

def fib_iter(n):                               # Θ(n) time, Θ(1) space: only the last two values
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b
    return a

print(fib_naive(25), calls)                    # 75025 242785   about 2.4 × 10⁵ calls for n = 25
print(fib_memo(25), fib_iter(25))              # 75025 75025
print(fib_iter(300) % 10**9)                   # 990979600      no stack, no cache, any n

Task: detect duplicates among n items	Time	Auxiliary space
Compare all pairs	Θ(n²)	Θ(1)
Sort in place (heapsort), then compare neighbors	Θ(n log n)	Θ(1)
Insert into a hash set	Θ(n) expected	Θ(n)

Key takeaways

• Space complexity measures the peak memory in use, usually counting only auxiliary space, and including the recursion stack.
• Space is never more than time (S = O(T)), but it can be much less.
• Recursion depth is a space cost. Converting tail-style recursion to a loop turns Θ(n) stack into Θ(1).
• Many problems offer a time–space trade-off: memoization and hashing spend memory to save time.

Practice

1. (Beginner) Give the auxiliary space of (a) reversing a list by building a new list, (b) reversing it in place with two pointers, and (c) recursive binary search.
2. (Intermediate) Show that quicksort uses only O(log n) stack space in the worst case if it recurses on the smaller part and loops on the larger part. Hint: every recursive call handles at most half of the current subarray.
3. (Interview) Detect whether a singly linked list contains a cycle using O(1) extra space. Hint: the obvious solution stores visited nodes in a set, which takes O(n) space. Instead, move two pointers through the list, one twice as fast as the other (Floyd's "tortoise and hare"). If there is a cycle, they must meet.

Worst, Best, and Average Case

Why. Even for a fixed size n, different inputs cost different amounts. Linear search might find its target at the first position or not at all. So the running time is not a function of n alone, and we must say which input of size n we mean. There are three standard choices, each answering a different question.

What. Let T(I) be the cost of the algorithm on input I, and let Dₙ be the set of inputs of size n.

Measure	Definition	Answers
Worst case	W(n) = max_{I ∈ Dₙ} T(I)	"How bad can it get?", a guarantee for every input
Best case	B(n) = min_{I ∈ Dₙ} T(I)	"How good can it get?", rarely useful on its own
Average case	A(n) = Σ_{I ∈ Dₙ} P(I)·T(I) = E[T]	"What is typical?", for an assumed probability distribution on inputs (7.3)

Always B(n) ≤ A(n) ≤ W(n). The average case depends on the distribution you assume, and a wrong assumption gives a wrong answer.

Example: linear search. Suppose the target is present and equally likely to be at each of the n positions. Finding it at position i costs i comparisons, so

  A(n) = (1/n)·(1 + 2 + … + n) = (n + 1)/2.

If the target is absent, the cost is always n. With a probability p that the target is present, A(n) = p·(n + 1)/2 + (1 − p)·n. Best case 1, worst case n, average about n/2: all three are linear except the best case.

Example: insertion sort. The best case (already sorted) takes n − 1 comparisons, and the worst case (reverse sorted) takes n(n − 1)/2. On a uniformly random permutation, the expected number of inversions is n(n − 1)/4 (indicator variables, 7.3), and the expected number of comparisons is exactly n(n − 1)/4 + n − H_n:

import random

def insertion_comparisons(a):
    a, comparisons = list(a), 0
    for i in range(1, len(a)):
        key, j = a[i], i - 1
        while j >= 0:
            comparisons += 1
            if a[j] <= key:
                break
            a[j + 1] = a[j]
            j -= 1
        a[j + 1] = key
    return comparisons

n, trials = 1000, 50
random.seed(7)
best = insertion_comparisons(range(n))                    # already sorted
worst = insertion_comparisons(range(n, 0, -1))            # reverse sorted
average = sum(insertion_comparisons(random.sample(range(n), n)) for _ in range(trials)) / trials
predicted = n * (n - 1) / 4 + n - sum(1 / k for k in range(1, n + 1))
print(best, worst, round(average), round(predicted))
# 999 499500 251183 250743           best Θ(n), worst Θ(n²), average ≈ n²/4: also Θ(n²)

Example: quicksort with the first element as pivot. On sorted input, every partition is maximally unbalanced, which gives Θ(n²) comparisons. On a random permutation, the average is about 1.39·n·log₂ n, which is Θ(n log n). The worst case is real: sorted and nearly sorted inputs are common in practice.

Four kinds of "average". These are often confused, and they give different guarantees:

Notion	Averaged over	Guarantee
Worst case	Nothing: the maximum over inputs	Every input
Average case	Random inputs from an assumed distribution	Typical inputs, if the assumption is right
Expected time of a randomized algorithm	The algorithm's own random choices, with the input fixed	Every input, in expectation (7.4)
Amortized	A sequence of operations	The total cost of any sequence

Why worst case is the default. It is a guarantee that needs no assumption about inputs. It is usually easier to compute than the average. For many algorithms it has the same order as the average anyway. And real inputs are often not random: they may be nearly sorted, or deliberately adversarial, as in hash-flooding attacks.

Key takeaways

• Worst case is the maximum cost over inputs of size n, best case the minimum, and average case the expectation under an assumed input distribution.
• Linear search: 1, (n + 1)/2, n. Insertion sort: n − 1, about n²/4, n(n − 1)/2.
• An average case is only as good as its distribution assumption. Randomizing the algorithm moves the randomness from the input to the algorithm, so its expected bound holds on every input.
• Amortized cost is a worst-case guarantee for sequences of operations, not an average over inputs.

Practice

1. (Beginner) Give the best-case and worst-case number of comparisons for (a) finding the maximum of n numbers and (b) binary search on 100 sorted elements.
2. (Intermediate) In linear search, the target is present with probability p and, when present, equally likely to be at each position. Show that the expected number of comparisons is n − p(n − 1)/2. Then suppose instead that the target is at position i with probability 2⁻ⁱ (for i < n, with the remaining probability on position n). Show that the expected cost is less than 2, and explain how the move-to-front heuristic exploits this kind of skew.
3. (Interview) A service has excellent median latency but terrible 99th-percentile latency. It sorts incoming batches with a quicksort that always uses the first element as pivot, and it stores session data in a hash map keyed by user-supplied strings. Which kinds of case analysis explain the symptom, and what would you change? Hint: the average case hides worst-case inputs. Batches that arrive nearly sorted, and crafted colliding keys, both trigger quadratic behavior. Consider a random pivot or introsort, and a randomized (seeded) hash function.

Tractable and Intractable Problems

Why. So far we have asked how fast a given algorithm is. Complexity theory asks a deeper question: how fast can any algorithm solve a given problem? The answer splits problems into ones we can solve in practice and ones that, as far as anyone knows, we cannot. Knowing which side your problem is on decides whether you should keep looking for a better algorithm or change your goal.

What. A problem is tractable if some algorithm solves it in polynomial worst-case time, O(nᵏ) for a constant k. The class of such decision problems is called P. A problem is intractable if no polynomial-time algorithm for it exists. A problem is unsolvable (undecidable) if no algorithm solves it at all, however much time it is given. The halting problem is the standard example (1.4, 13.4).

Why polynomial time is the dividing line (the Cobham–Edmonds thesis):

• Exponential growth defeats hardware. As Common Growth Rates showed, a faster computer multiplies the feasible input size of a polynomial algorithm, but only adds a constant to that of an exponential one.
• Closure. A polynomial-time algorithm that calls a polynomial-time subroutine a polynomial number of times is still polynomial, because a polynomial of a polynomial is a polynomial. So tractable building blocks combine into tractable systems.
• Robustness. Every reasonable model of computation (the RAM model, Turing machines in 13.4, real programming languages) can simulate every other one with polynomial overhead. The class P does not depend on the model.
• Experience. When a polynomial algorithm is found for a natural problem, its exponent is usually small (n, n log n, n³), and it usually improves over time.

Caveats. The line is a theoretical idealization. An n¹⁰⁰ algorithm is useless, while a 1.0001ⁿ algorithm is fine for n ≤ 10⁴. The simplex method for linear programming takes exponential time in the worst case, but it is fast on almost every real instance. Modern SAT solvers routinely solve industrial instances with millions of variables, although SAT is believed intractable in the worst case.

The landscape of problems.

Category	Meaning	Examples
Tractable (in P)	A polynomial-time algorithm is known	Sorting, shortest paths (8.4), minimum spanning trees (9.4), maximum matching (8.6), 2-SAT (1.1), primality testing (AKS, 2002)
Believed intractable	No polynomial algorithm is known, and none has been ruled out	SAT (1.1), Hamiltonian cycle and TSP (8.4), 3-coloring (8.5), subset sum, integer factoring
Provably intractable	Every algorithm needs exponential time	Generalized chess and Go on n × n boards. Any problem whose output is exponentially long: listing all 2ⁿ subsets, or the 2ⁿ − 1 moves of the Tower of Hanoi (6.1)
Unsolvable	No algorithm exists	The halting problem (1.4, 13.4). Hilbert's tenth problem: whether a polynomial equation has a solution in integers

Example: subset sum. Given integers a₁, …, aₙ and a target T, is there a subset that sums to T? Brute force tries all 2ⁿ subsets. Dynamic programming tracks which sums up to T are reachable, in O(n·T) time:

from itertools import combinations

def subset_sum_brute(a, target):              # tries all 2ⁿ subsets: Θ(2ⁿ·n) in the worst case
    return any(sum(c) == target
               for r in range(len(a) + 1) for c in combinations(a, r))

def subset_sum_dp(a, target):                 # O(n·target): at most target + 1 reachable sums
    reachable = {0}
    for x in a:
        reachable |= {s + x for s in reachable if s + x <= target}
    return target in reachable

a = [3, 34, 4, 12, 5, 2]
print(subset_sum_brute(a, 9), subset_sum_dp(a, 9))      # True True     4 + 5
print(subset_sum_brute(a, 30), subset_sum_dp(a, 30))    # False False   without 34 the total is only 26

O(n·T) looks polynomial, but T is a value. Its input length is only log₂ T bits, so O(n·T) is exponential in the input length. The algorithm is pseudo-polynomial, like trial division. It is excellent for amounts in cents up to 10⁶, and hopeless for 64-bit values, where T can be about 1.8 × 10¹⁹. Subset sum is NP-complete (next topic), and the DP does not contradict that.

Key takeaways

• Tractable means solvable in polynomial time. That class, P, is robust across machine models and closed under composition.
• Problems are tractable, believed intractable, provably intractable, or unsolvable.
• Pseudo-polynomial algorithms, such as the subset-sum DP or trial division, are polynomial in the numeric value of the input but exponential in its length.
• The polynomial/exponential line is an idealization: large exponents and good heuristics both blur it in practice.

Practice

1. (Beginner) Classify each problem as tractable, believed intractable, provably intractable or unsolvable: sorting a list of names; listing every permutation of n items; deciding whether an arbitrary program halts on every input; finding a shortest path in a road network; deciding whether a graph can be 3-colored.
2. (Intermediate) Explain why the subset-sum DP does not show that P = NP, although subset sum is NP-complete. How many bits does the input (a₁, …, aₙ, T) take, and how does the running time compare with that length?
3. (Interview) A product manager wants the provably optimal delivery route through 200 stops for each driver, computed in under a second. How do you respond? Hint: this is TSP (8.4), and 199!/2 tours rule out brute force. Offer heuristics (nearest neighbor followed by 2-opt improvements), approximation algorithms with guarantees for road-like (metric) distances, or a dedicated solver with a time limit that reports how far its answer can be from optimal.

P, NP, and NP-Completeness

Why. Hundreds of important problems, in scheduling, routing, packing, circuit verification, register allocation and protein folding, have resisted every attempt to find polynomial-time algorithms for more than fifty years. NP-completeness explains why. These problems are all equivalent: a polynomial algorithm for any one of them would give polynomial algorithms for all of them. Showing that your problem is NP-complete is strong evidence that you should stop looking for an exact, fast, general algorithm, and choose a different strategy.

What.

• A decision problem has a yes/no answer: "Does G have a Hamiltonian cycle?", "Is there a tour of weight at most B?". An optimization problem usually reduces to its decision version by binary search on the bound B.
• P is the class of decision problems solvable in polynomial time.
• NP is the class of decision problems whose yes-instances have a certificate (a proof, or witness) of polynomial length that can be checked in polynomial time. The name means nondeterministic polynomial time: a machine that could guess the certificate would only need to verify it. NP does not stand for "not polynomial".
• P ⊆ NP: a polynomial-time solver is also a verifier that ignores the certificate.

Problem	Certificate for a "yes" answer	Verification
SAT (1.1)	A truth assignment	Evaluate every clause: linear in the formula size
Hamiltonian cycle (8.4)	An ordering of the vertices	Each vertex appears once, and consecutive vertices are adjacent: O(n + m)
k-coloring (8.5)	A color for each vertex	Both ends of every edge differ: O(n + m)
Subset sum	The subset	Add it up
Composite number	A nontrivial factor	One division

Finding a certificate seems to require search, while checking one is easy. The question P = NP? asks whether finding is ever really harder than checking. It is the most famous open problem in computer science, and one of the Clay Mathematics Institute's seven Millennium Prize Problems. Most researchers believe that P ≠ NP.

Reductions. A polynomial-time reduction from problem A to problem B, written A ≤ₚ B, is a polynomial-time function f that maps instances of A to instances of B so that

  x is a yes-instance of A   ⟺   f(x) is a yes-instance of B.

It means "B is at least as hard as A": a fast algorithm for B gives a fast algorithm for A (apply f, then solve B). If A ≤ₚ B and B ∈ P, then A ∈ P.

• A problem B is NP-hard if every problem in NP reduces to it.
• A problem is NP-complete if it is NP-hard and belongs to NP. The NP-complete problems are the hardest problems in NP.
• Cook–Levin theorem (1971): SAT is NP-complete.

How to prove that a new problem B is NP-complete:

1. Show that B ∈ NP: describe a certificate and a polynomial-time verifier.
2. Choose a known NP-complete problem A and give a polynomial-time reduction A ≤ₚ B. The direction matters. Reducing B to SAT only shows that B is no harder than SAT, which is true of every problem in NP.

Karp (1972) used this method to show that 21 classic problems are NP-complete. Thousands more have followed, by chains of reductions such as:

                         SAT          (Cook–Levin: every NP problem reduces to SAT)
                          │
                        3-SAT
           ┌──────────────┼──────────────────┐
         Clique       3-Coloring         Subset Sum
           │                                 │
    Independent Set                      Knapsack
           │
      Vertex Cover
           │
   Hamiltonian Cycle
           │
          TSP

Example reduction: Independent Set ≤ₚ Vertex Cover. An independent set is a set of vertices with no edge between any two of them. A vertex cover is a set of vertices that touches every edge.

Claim. S is an independent set of G = (V, E) if and only if V − S is a vertex cover. Proof. S is independent ⟺ no edge has both endpoints in S ⟺ every edge has at least one endpoint in V − S ⟺ V − S is a vertex cover. ∎

So the map (G, k) ↦ (G, n − k) is a reduction: G has an independent set of size k exactly when it has a vertex cover of size n − k. Similarly, a clique in G is an independent set in the complement graph (8.1), which gives Clique ≤ₚ Independent Set.

from itertools import combinations

def verify_coloring(n, edges, coloring, k):          # an NP verifier: O(n + m) time
    return (len(coloring) == n and all(0 <= c < k for c in coloring)
            and all(coloring[u] != coloring[v] for u, v in edges))

def has_independent_set(n, edges, k):                # brute force over all C(n, k) sets: exponential
    return any(not any(u in S and v in S for u, v in edges)
               for S in map(set, combinations(range(n), k)))

def has_vertex_cover(n, edges, k):
    return any(all(u in C or v in C for u, v in edges)
               for C in map(set, combinations(range(n), k)))

n = 5
edges = [(0, 1), (1, 2), (2, 3), (3, 4), (4, 0), (0, 2)]   # a 5-cycle with the chord 0–2
print(verify_coloring(n, edges, [0, 1, 2, 0, 1], 3))       # True:  a valid 3-coloring (certificate accepted)
print(verify_coloring(n, edges, [0, 1, 0, 1, 2], 3))       # False: edge 0–2 has two endpoints of color 0
print([(k, has_independent_set(n, edges, k), has_vertex_cover(n, edges, n - k))
       for k in range(n + 1)])
# [(0, True, True), (1, True, True), (2, True, True), (3, False, False), (4, False, False), (5, False, False)]

The two columns agree for every k, as the reduction promises. The largest independent set has size 2, so the smallest vertex cover has size 3.

The picture, assuming P ≠ NP.

  ┌─────────────────────────── NP ──────────────────────────────┐
  │                                                             │
  │  ┌─────────── P ─────────────┐               ┌──────────────┼────── NP-hard ────────┐
  │  │ sorting, shortest         │  factoring?   │ NP-complete  │                       │
  │  │ paths, MST, matching,     │  graph        │ SAT, 3-SAT,  │  halting problem,     │
  │  │ 2-SAT, primality          │  isomorphism? │ 3-COL, HAM-  │  TSP as an            │
  │  │                           │               │ CYCLE, TSP   │  optimization         │
  │  └───────────────────────────┘               │ (decision)   │  problem              │
  │                                              │              │                       │
  └──────────────────────────────────────────────┼──────────────┘                       │
                                                 └──────────────────────────────────────┘

NP-complete problems are exactly the intersection of NP and NP-hard. Ladner's theorem (1975) says that if P ≠ NP, some problems in NP are neither in P nor NP-complete. Integer factoring and graph isomorphism (8.2) are the best-known candidates. Neither is known to be in P, and neither is believed to be NP-complete. If P = NP, the whole of NP collapses into P, and every NP problem becomes NP-complete except the two trivial ones (always yes, always no).

Why it matters. If P = NP with a practical algorithm, then finding a secret key would be as easy as checking it, and most public-key cryptography (4.4) would collapse. Mathematics would change too, because finding a proof of bounded length would be as easy as checking one. The reverse is not automatic: RSA relies on factoring, which might be easy even if P ≠ NP.

Coping with NP-complete problems. NP-completeness is a statement about exact, general, worst-case algorithms. Relax any of these three words and there are good options:

Strategy	Idea	Example
Special cases	Restricted inputs may be in P	2-SAT and Horn-SAT (1.1), coloring bipartite graphs, most problems on trees
Exact exponential search	Backtracking, branch and bound, dynamic programming over subsets	Held–Karp solves TSP in O(n²·2ⁿ), far better than n!
Approximation algorithms	Polynomial time with a proven ratio to the optimum	Vertex cover within a factor of 2 (take both ends of a maximal matching, 8.6). Metric TSP within 2 by walking around an MST (9.4)
Fixed-parameter algorithms	Exponential only in a small parameter k	Vertex cover of size k in O(2ᵏ·(n + m))
Heuristics	No guarantee, good results in practice	2-opt for TSP, greedy coloring (8.5), local search
Solvers	Encode the problem for a SAT or integer-programming solver	Hardware verification, scheduling, package dependency resolution

Key takeaways

• P contains the problems that are solvable in polynomial time. NP contains the problems whose yes-answers can be verified in polynomial time from a certificate. P ⊆ NP, and whether they are equal is open.
• A ≤ₚ B means that B is at least as hard as A. NP-hard problems are at least as hard as everything in NP, and NP-complete problems are NP-hard problems that lie in NP.
• To prove that B is NP-complete, show that B ∈ NP and reduce a known NP-complete problem to B.
• SAT, 3-SAT, clique, independent set, vertex cover, Hamiltonian cycle, TSP, 3-coloring and subset sum are all NP-complete.
• NP-completeness rules out exact, fast, general algorithms (unless P = NP). It does not rule out special cases, approximation, parameterized algorithms, or solvers that work well in practice.

Practice

1. (Beginner) For each problem, describe a certificate and how long it takes to verify: (a) "G has a clique of size k"; (b) "G is not 2-colorable"; (c) "N is composite". Which of these problems are known to be in P?
2. (Intermediate) Prove that Clique ≤ₚ Independent Set using the complement graph, and check that the reduction runs in polynomial time. Then explain precisely why a reduction from your new problem to SAT proves nothing about its hardness.
3. (Interview) A teammate says they have found a polynomial-time algorithm that assigns exams to k time slots so that no student has two exams in the same slot, for any k and any enrollment data. How do you respond? Hint: model exams as vertices and shared students as edges. The task is graph k-coloring (8.5), which is NP-complete for k ≥ 3, so a correct general algorithm would prove P = NP. Ask for the proof of correctness, look for small inputs that break it, and check whether the real data has special structure the algorithm exploits.

<a id="11-boolean-algebra"></a>