--- title: Algorithms source: 'https://academia.sh/en/courses/algorithms' language: en updated: '2026-08-17T04:39:26+00:00' license: 'CC BY-SA 4.0' lessons: 25 outcomes: - 'Expresses the time and space complexity of an algorithm in asymptotic notation' - 'Compares sorting and searching algorithms along the axes of correctness and cost' - 'Applies classical graph and text algorithms to suitable problems' --- # Algorithms From asymptotic analysis to sorting, searching, graph and text algorithms; comparing solutions along the axes of correctness and cost. ## Algorithm Analysis Algorithm criteria, asymptotic notations, complexity classes, and cost calculation methods. ### What Is an Algorithm Source: https://academia.sh/en/courses/algorithms/what-is-an-algorithm The criteria for an algorithm, the distinction between correctness and termination, the model of computation, and why measuring running time is not enough. The Data Structures course established how data is organized and how that organization determines cost. Cost expressions — $O(1)$, $O(\log n)$, $O(n)$ — were used but not defined; they were explained only intuitively, as "the rate at which cost grows as data grows." This course closes that gap and turns the question around: what is examined is not the data but the **solution**. How are different solutions to the same problem compared, and what is the comparison based on? #### The Criteria for an Algorithm An **algorithm** is a finite sequence of steps that solves a problem. Short as this definition is, five criteria are required for a method to count as an algorithm: **Input.** It takes zero or more well-defined inputs. **Output.** It produces at least one output, and that output is related to the input. **Determinism.** Every step has a single meaning; the same input executes the same steps in the same order. The determinism discussion from the Programming Fundamentals course connects here. **Finiteness.** It halts in a finite number of steps for every valid input. A method that enters an infinite loop is not an algorithm. **Effectiveness.** Every step must be executable in finite time with well-defined means. "Find the right answer" is not a step; "scan the array from start to end" is a step. The five criteria do not cover everything called an "algorithm" in everyday language. Randomized methods relax the determinism criterion; approximate methods relax the exactness of the output. These relaxations are stated explicitly wherever they apply. #### Problem, Instance, and Program These three concepts are often confused, and their distinction is assumed throughout the rest of this course. A **problem** is the specification of the relationship between inputs and acceptable outputs: "the input is an array of integers; the output is the same elements arranged in nondecreasing order." A specification does not state a method; it only states what counts as correct. An **instance** is a single input to the problem: the array `[5, 2, 9]` is an instance. An algorithm must solve **every** instance, not a single one; giving the right answer on one particular input is not enough. A **program** is an implementation of an algorithm, written in a particular language for a particular machine. The same algorithm can have countless programs; they are all the same algorithm as long as they follow the same steps. This distinction determines what correctness is measured against: an algorithm is correct not relative to a program but relative to the **problem specification**. This is why algorithms are usually written in pseudocode — language details are irrelevant to the specification. #### Correctness Has Two Parts Saying an algorithm is correct makes two separate claims: **Partial correctness:** If the algorithm **halts**, the result is correct. **Termination:** The algorithm halts for every valid input. Together the two give **total correctness**. The distinction lets proofs be split into two separate parts as well, and this split is useful in practice — there are methods that satisfy one but not the other. The standard tool for partial correctness is the **loop invariant**, introduced in the Programming Fundamentals course: if a condition is true before the loop is entered, preserved on every iteration, and yields the desired result when the loop ends, partial correctness has been proved. The standard tool for termination is a **decreasing measure**: if a value can be found that strictly decreases on every iteration and is bounded from below, the loop cannot continue forever. ```python def find_largest(measurements: list[int]) -> int: """Returns the largest measurement. The list must not be empty. Invariant: at the start of every iteration, `largest` is the largest of the elements visited so far. Termination: the number of remaining elements decreases by one every iteration. """ largest = measurements[0] for measurement in measurements: if measurement > largest: largest = measurement return largest print(find_largest([12, 18, 7, 25, 14])) # 25 ``` The two lines in the docstring are not decoration: one is the justification for partial correctness, the other for termination. Showing that an algorithm is correct means being able to write these two sentences. #### Same Problem, Different Algorithms A problem can have more than one solution, and solutions differ not only in speed but in **structure**. ```python def sum_loop(n: int) -> int: """The sum of the numbers from 1 to n; each number added one at a time.""" total = 0 for i in range(1, n + 1): total += i return total def sum_formula(n: int) -> int: """The same sum; in a single step with a closed-form formula.""" return n * (n + 1) // 2 print(sum_loop(100), sum_formula(100)) # 5050 5050 print(sum_loop(1_000_000) == sum_formula(1_000_000)) # True ``` The two functions give the same result. The first does $n$ additions; the second does one multiplication, one addition, and one division — regardless of the input. The difference is not an optimization detail: the first solution's cost grows with the input, the second's does not. For a million, the first does a million operations, the second does three. This makes the course's central question concrete: **how do we measure** the difference between two solutions? #### Why Measuring Time Is Not Enough The first metric that comes to mind is running time. But time depends on three factors at once, and none of them belongs to the algorithm itself. **Hardware.** The same program takes different amounts of time on different processors; the memory hierarchy from the How Computers Work course was one source of this difference. **Implementation.** Choices of language, compiler, and runtime change duration by multiples. In the cache measurement from the Data Structures course, this effect was large enough to hide what was meant to be measured. **Input.** The same algorithm takes different amounts of time on different inputs; a sorted array and a scrambled array behave very differently under the same sorting algorithm. A measurement is therefore not a **property** of an algorithm but an observation of a particular run. For a comparison to be portable, a metric independent of hardware and language is needed. #### Model of Computation and Operation Counting The solution is to adopt an abstract **model of computation**. The model used in this course rests on these assumptions: - Basic operations — addition, comparison, assignment, index access — take constant time. - Memory access has the same cost regardless of location. - Operations execute one after another. The model is a simplified version of reality: cache layers and the instruction pipeline are ignored. In return, algorithms become comparable independently of hardware. The metric follows from this: **the number of basic operations performed as a function of input size.** ```python def linear_search(array: list[int], target: int) -> tuple[int, int]: """Returns (index found or -1, comparison count).""" comparisons = 0 for i, value in enumerate(array): comparisons += 1 if value == target: return i, comparisons return -1, comparisons array = list(range(1000)) print(linear_search(array, 0)) # (0, 1) — best case print(linear_search(array, 999)) # (999, 1000) — worst case print(linear_search(array, -1)) # (-1, 1000) — not found ``` The same algorithm, at the same input size, does anywhere from 1 to 1000 operations. For this reason, three separate metrics are defined instead of a single number: - **Best case:** The input that requires the fewest operations. - **Worst case:** The input that requires the most operations. - **Average case:** The expected number of operations over a probability distribution of inputs. The default metric is the **worst case**; it gives a guarantee and requires no assumption about distribution. Average case is meaningful when the distribution is actually known — the hash table's "average constant" promise was exactly this kind of claim. #### Summary - An algorithm is a finite sequence of steps that meets the criteria of input, output, determinism, finiteness, and effectiveness. - A problem is a specification, an instance is a single input, a program is an implementation; correctness is measured against the specification. - Correctness has two parts: partial correctness (the result is correct if it halts) is justified with a loop invariant, and termination (it halts for every input) with a decreasing measure. - Solutions to the same problem differ in structure; the difference shows up in whether cost grows with the input or not. - Running time depends on hardware, implementation, and input; it is not a property of the algorithm. - The metric is the number of basic operations performed as a function of input size in an abstract model, and best, worst, and average case are treated separately. #### Next Step Operation counting is a step in the right direction, but it still drowns in detail: in a thousand-element array, whether 1000 or 1002 comparisons were made does not matter. The next lesson eliminates this detail and formally defines the notation that keeps only the growth rate — asymptotic notation. ### Asymptotic Notation Source: https://academia.sh/en/courses/algorithms/asymptotic-notation Definitions of big O, big omega, and big theta, elimination of constants, sum and product rules, and common misreadings. The previous lesson settled on operation count as the metric but left a problem: in a thousand-element array, whether 1000 or 1002 comparisons were made does not matter. These details depend on the implementation; what belongs to the algorithm itself is **the rate at which the operation count grows as the input grows**. Asymptotic notation is the language that captures this rate and discards the rest. #### Big O: Upper Bound Let $f$ and $g$ be functions from positive integers to positive real numbers. $$ f(n) = O(g(n)) \iff \exists\, c > 0,\ n_0 \in \mathbb{N} : \forall n \geq n_0,\ f(n) \leq c \cdot g(n) $$ In words: if, for **sufficiently large** $n$, $f$ never exceeds a constant multiple of $g$, then $f$ grows at most as fast as $g$. Both quantifiers in the definition are necessary. The constant $c$ eliminates factor-of differences — an implementation that runs twice as fast stays in the same class. The threshold $n_0$ eliminates irregularities at small inputs; an asymptotic statement is a claim about large inputs. This can be shown explicitly with an example. For $f(n) = 3n^2 + 5n + 20$, choosing $g(n) = n^2$, the values $c = 4$ and $n_0 = 8$ satisfy the definition: ```python def f(n: int) -> int: return 3 * n**2 + 5 * n + 20 c, n0 = 4, 8 print(f(7) <= c * 7**2) # False — not satisfied below the threshold print(f(8) <= c * 8**2) # True print(all(f(n) <= c * n**2 for n in range(n0, 10_000))) # True ``` That it does not hold at seven is not a problem: the definition says something about **what comes after the threshold**. From eight onward, the inequality always holds; hence $3n^2 + 5n + 20 = O(n^2)$ is written. #### Big Omega: Lower Bound $$ f(n) = \Omega(g(n)) \iff \exists\, c > 0,\ n_0 : \forall n \geq n_0,\ f(n) \geq c \cdot g(n) $$ Big O gives a ceiling, big omega gives a floor. It is used to say "this algorithm does at least this much work." Lower bounds are powerful when they are stated for a **problem**, not for a single algorithm: the statement "comparison-based sorting requires at least $\Omega(n \log n)$ comparisons" says that no comparison-based algorithm can go below this bound. This kind of result will be taken up together with the proof idea in the searching and sorting topic. #### Big Theta: Tight Bound $$ f(n) = \Theta(g(n)) \iff f(n) = O(g(n)) \ \text{ and } \ f(n) = \Omega(g(n)) $$ Theta says that growth is **exactly** on the order of $g$: both the ceiling and the floor are the same function. The expression $3n^2 + 5n + 20$ is $\Theta(n^2)$. The same expression is also $O(n^3)$ — an upper bound may be loose — but it is not $\Theta(n^3)$. In everyday use, big O is often written while meaning a tight bound. This is a convenience; where precision matters, theta is preferred. #### Simplification Rules Complexity expressions simplify by a few rules. **Constant factors are eliminated.** $O(3n) = O(n)$. The constant is already absorbed by the $c$ in the definition. **In a sum, the largest term remains.** $O(n^2 + n) = O(n^2)$. Whichever of two sequential parts is more expensive is decisive. **In a product, factors are preserved.** Costs multiply in nested loops: $O(n) \cdot O(\log n) = O(n \log n)$. **Transitivity holds.** If $f = O(g)$ and $g = O(h)$, then $f = O(h)$. | Expression | Simplified | Reason | |---|---|---| | $5n + 100$ | $O(n)$ | Constants and the constant term are eliminated | | $n^2 + 1000n$ | $O(n^2)$ | The larger term dominates | | $\log_2 n$ and $\log_{10} n$ | The same $O(\log n)$ | A base change is a constant factor | | $2^{n+1}$ | $O(2^n)$ | $2^{n+1} = 2 \cdot 2^n$ | | $n!$ and $2^n$ | Different classes | Factorial grows faster than exponential | The third row answers a frequently asked point: a logarithm's base is not specified, because a base change produces only a constant factor, and that factor is eliminated. #### Finding the Constant and the Threshold Proving a claim means **producing** a suitable $c$ and $n_0$. For polynomials there is a mechanical method: for $n \geq 1$, every lower-degree term is bounded by the dominant term, and the coefficients are summed. In the example $f(n) = 3n^2 + 5n + 20$, for $n \geq 1$ it can be written that $5n \leq 5n^2$ and $20 \leq 20n^2$. Summed, this gives $f(n) \leq 28n^2$; that is, $c = 28$, $n_0 = 1$ is also a valid pair that satisfies the definition. Above, a smaller constant was found with $c = 4$, but it was not necessary: the definition asks for the existence of **a** pair, not the smallest one. This explains why asymptotic claims are easy to prove — even a crude bound suffices. #### Common Misreadings **"$O(n)$ does not mean exactly $n$ operations."** It is an upper bound; $3n$ and $n/2$ are both $O(n)$. **"$O$ does not mean worst case."** These are two separate axes. $O$, $\Omega$, and $\Theta$ can each be written separately for the best, worst, and average case. "$O(n^2)$ in the worst case" and "$O(n^2)$ in every case" are different claims. **"A smaller class is not always better."** Because asymptotic notation eliminates constants, an $O(n \log n)$ algorithm can be slower than an $O(n^2)$ algorithm on small inputs. This is why sorting libraries apply a different algorithm to small chunks. **The notation is not an equality.** The way of writing $f(n) = O(g(n))$ is established but misleading; correctly, it is set membership of the form $f \in O(g)$. For this reason the equality is not symmetric: $O(n) = f(n)$ is not written. #### What Is Input Size One last definition is needed: what does $n$ count? The answer varies by problem, and the expression is meaningless if it is not specified. - In array operations, the number of elements. - In text algorithms, the number of characters. - In graph algorithms, both the number of nodes and the number of edges — this is why costs are written with two variables, as in $O(V + E)$. - In numerical algorithms, usually the number's **bit length**; not the number itself. The last item is a subtle distinction. A method that tests whether a number is prime by dividing up to the number itself appears to be $O(\sqrt{N})$ if the number's value is taken as the input; but the input is not $N$, it is the number of bits needed to write it. In terms of bit length, the same method is exponential. This distinction is the foundation of classification in complexity theory and is taken up in the **Theory of Computation** course. #### Summary - Asymptotic notation eliminates constants and lower-order terms, keeping only the growth rate. - Big O gives an upper bound, big omega a lower bound, big theta a tight bound. - The constant $c$ in the definition eliminates factor-of differences, and the threshold $n_0$ eliminates small inputs. - In simplification, constants are eliminated, the largest term remains in a sum, and factors are preserved in a product; a logarithm's base is not written, because a base change is a constant factor. - $O$ and "worst case" are different axes; a smaller asymptotic class does not guarantee being fast on small inputs. - What is counted as input size must be stated explicitly. #### Next Step Big O and omega do not say whether a bound is tight: $n$ is both $O(n)$ and $O(n^2)$. The next lesson will define the little notations that state a bound is strictly loose, and show what statements they make possible. ### Little o and Little omega Source: https://academia.sh/en/courses/algorithms/little-o-and-little-omega Definitions of non-tight bounds, the limit criterion, the analogy between the five notations and comparison operators, and the limits of the ordering relation. Big O gives an upper bound but does not say whether the bound is **tight**. The function $n$ is both $O(n)$ and $O(n^2)$; the second statement is true but uninformative. In some cases, what needs to be said is stronger: "$f$ grows **strictly** slower than $g$." This lesson defines the two notations that make that statement possible. #### Little o $$ f(n) = o(g(n)) \iff \forall c > 0,\ \exists n_0 : \forall n \geq n_0,\ f(n) < c \cdot g(n) $$ Its difference from big O is in the quantifier. Big O says "**a** $c$ exists"; little o says "**for every** $c$" — no matter how small the constant is chosen, the inequality holds for sufficiently large $n$. The result is that $f$ becomes **increasingly negligible** next to $g$. An equivalent and useful form is given with a limit: $$ f(n) = o(g(n)) \iff \lim_{n \to \infty} \frac{f(n)}{g(n)} = 0 $$ For example, $n = o(n^2)$, because the ratio $1/n \to 0$. By contrast, $3n$ is **not** $o(n)$: the ratio stays at the constant $3$, it does not go to zero. Big O, however, accepts both — $3n = O(n)$ is true. #### Little omega $$ f(n) = \omega(g(n)) \iff \lim_{n \to \infty} \frac{f(n)}{g(n)} = \infty $$ Little omega is little o's mirror image: $f$ strictly outpaces $g$. $n^2 = \omega(n)$ and $2^n = \omega(n^{100})$ are true — exponential growth eventually overtakes every polynomial. #### The Analogy of the Five Notations The five notations map one to one onto numeric comparisons: | Notation | Comparison analogy | Limit criterion | |---|---|---| | $f = O(g)$ | $f \leq g$ | Ratio finite (can be zero) | | $f = \Omega(g)$ | $f \geq g$ | Ratio greater than zero (can be infinite) | | $f = \Theta(g)$ | $f = g$ | Ratio tends to a finite constant greater than zero | | $f = o(g)$ | $f < g$ | Ratio tends to zero | | $f = \omega(g)$ | $f > g$ | Ratio tends to infinity | The analogy is instructive but not exact; the differences are taken up in the final section of this lesson. #### Applying the Limit Criterion The limit is the most practical way to determine the relationship between two functions. The ratio is computed and its behavior as it tends to infinity is examined. ```python import math def ratio(f, g, n_values): return [f(n) / g(n) for n in n_values] n_values = [10, 100, 1_000, 10_000, 100_000] print([f"{x:.4f}" for x in ratio(lambda n: n, lambda n: n**2, n_values)]) # ['0.1000', '0.0100', '0.0010', '0.0001', '0.0000'] — tends to zero: n = o(n²) print([f"{x:.4f}" for x in ratio(lambda n: 3*n, lambda n: n, n_values)]) # ['3.0000', '3.0000', '3.0000', '3.0000', '3.0000'] — constant: 3n = Θ(n), not o(n) print([f"{x:.4f}" for x in ratio(math.log2, lambda n: n, n_values)]) # ['0.3322', '0.0664', '0.0100', '0.0013', '0.0002'] — tends to zero: log n = o(n) print([f"{x:.2f}" for x in ratio(lambda n: n * math.log2(n), lambda n: n**2, n_values)]) # ['0.33', '0.07', '0.01', '0.00', '0.00'] — n log n = o(n²) ``` A numerical observation is not a proof; that the limit actually goes to zero is shown mathematically. But it is a fast way to confirm an expectation and catch errors. The third line confirms a frequently used result: **a logarithm grows slower than every positive power.** The fourth line shows why the difference between $n \log n$ and $n^2$ is so decisive — the ratio tends to zero, meaning the gap widens as the input grows. #### Growth Hierarchy Little o arranges frequently used functions into a strict chain. At every step, the one on the left is little o of the one on the right: $$ 1 = o(\log \log n) = o(\log n) = o(n^{\varepsilon}) = o(n) = o(n \log n) = o(n^2) = o(2^n) = o(n!) $$ Here $\varepsilon$ is any constant greater than zero. The chain summarizes three general rules: - **Logarithm grows slower than every positive power.** Even $\log n = o(n^{0.001})$ holds; it does not matter how many times the logarithm is applied. - **Every polynomial grows slower than every exponential.** $n^{1000} = o(1.001^n)$ holds, no matter how close the base is to one. - **Exponential grows slower than factorial.** The average of $n!$'s factors grows along with $n$, while $2^n$'s factors stay constant. Because every relation in the chain is written with little o, the distinctions between them are strict; moving from one class to another is not a constant-factor improvement but a change of order. The same chain also gives the link between $\Theta$ and the little notations: if $f = \Theta(g)$, then $f$ is neither $o(g)$ nor $\omega(g)$. The three cases are mutually exclusive and — if the limit of the ratio exists — together cover every possibility. #### What It Is For Little notations are used in three places. **Establishing the class hierarchy.** The statements "$\log n = o(n)$ and $n = o(n^2)$" say that complexity classes are strictly separated. The same claim cannot be made with big O; because $O$ may be loose, it does not demonstrate the distinction. **Stating negligibility.** If an expression's smaller term is written with $o(\cdot)$, this states "this term is asymptotically insignificant": the expression $n^2 + o(n^2)$ states that the second term vanishes next to the dominant term. **A claim of strict separation.** That two algorithms are in different classes can only be stated with little notation. "The first is $O(n^2)$, the second is $O(n \log n)$" does not by itself prove the second is better — the first's bound might be loose. The precise statement is that the second algorithm's cost is $o(\cdot)$ of the first's. #### Not a Total Order The comparison analogy breaks down at one point: for numbers, one of two values is always either smaller than, larger than, or equal to the other. For functions, there is no such guarantee. Two functions can be **incomparable**: if the ratio between them oscillates, neither a limit exists nor can a bound relation be established. For example, there is no asymptotic relation at all between $n$ and a function that takes the value $n^2$ at odd $n$ and $1$ at even $n$. ```python def oscillating(n: int) -> int: return n**2 if n % 2 == 1 else 1 print([oscillating(n) / n for n in range(1, 8)]) # [1.0, 0.5, 3.0, 0.25, 5.0, 0.16666666666666666, 7.0] — ratio oscillates ``` The ratio converges to neither zero nor infinity; it goes back and forth between them. Such a function is neither $O(n)$ nor $\Omega(n)$. Algorithm costs encountered in practice are regular functions, and this problem does not arise; but knowing that the notation is a **partial order** requires constructing statements carefully. #### Summary - Little o states that a bound is strictly loose: the inequality holds for every constant, and the ratio tends to zero. - Little omega is the same relation in reverse; the ratio tends to infinity. - The five notations resemble numeric comparisons: $O \approx \leq$, $\Omega \approx \geq$, $\Theta \approx =$, $o \approx <$, $\omega \approx >$. - The limit criterion is the practical way to determine the relationship between two functions. - Little notations are used to establish the class hierarchy, state negligibility, and make a claim of strict separation. - The relation is not a total order; functions whose ratio oscillates are incomparable. #### Next Step The notations have been defined; next comes the growth classes they represent. The next lesson will compare, numerically, the classes stretching from constant time to factorial, and answer the question "how large an input can an algorithm handle." ### Reading Complexity Classes Source: https://academia.sh/en/courses/algorithms/complexity-classes Constant, logarithmic, linear, linearithmic, polynomial, exponential, and factorial growth; scaling behavior and practical limits. The notations have been defined; this lesson makes concrete the growth classes they represent. The goal is to know **numerically** what a cost expression means on sight: whether an $O(n^2)$ algorithm can work with a million elements is a matter of calculation, not guesswork. #### Classes The commonly encountered classes, from slowest to fastest growing: | Class | Name | Typical example | |---|---|---| | $O(1)$ | Constant | Array element access, hash table lookup | | $O(\log n)$ | Logarithmic | Binary search, search in a balanced tree | | $O(n)$ | Linear | Scanning an array, finding the largest | | $O(n \log n)$ | Linearithmic | Efficient sorting algorithms | | $O(n^2)$ | Quadratic | Two nested loops, elementary sorts | | $O(n^3)$ | Cubic | Three-dimensional nested loop, naive matrix multiplication | | $O(2^n)$ | Exponential | Trying every subset | | $O(n!)$ | Factorial | Trying every ordering | There are also classes in between — such as $O(\sqrt{n})$, $O(n \log \log n)$, $O(n^{2.37})$ — but the list above covers most of practice. #### Numerical Comparison The difference between classes becomes visible once a few numbers are written down. ```python import math def operation_count(n: int) -> dict[str, float]: return { "log n": math.log2(n), "n": n, "n log n": n * math.log2(n), "n²": n**2, "2ⁿ": 2**n if n <= 40 else float("inf"), } for n in (10, 100, 1_000, 1_000_000): d = operation_count(n) print(n, {k: f"{v:.3g}" for k, v in d.items()}) # 10 {'log n': '3.32', 'n': '10', 'n log n': '33.2', 'n²': '100', '2ⁿ': '1.02e+03'} # 100 {'log n': '6.64', 'n': '100', 'n log n': '664', 'n²': '1e+04', '2ⁿ': 'inf'} # 1000 {'log n': '9.97', 'n': '1e+03', 'n log n': '9.97e+03', 'n²': '1e+06', '2ⁿ': 'inf'} # 1000000 {'log n': '19.9', 'n': '1e+06', 'n log n': '1.99e+07', 'n²': '1e+12', '2ⁿ': 'inf'} ``` At a million elements, a logarithmic algorithm takes **twenty** steps; a quadratic algorithm takes **a trillion**. The difference is not "a bit slower" — it is the difference between a problem being solvable and not. That the exponential column is not computed above forty is not a convenience but a necessity: $2^{100}$ is about $1.3 \times 10^{30}$, and a machine running a billion steps a second would need thousands of times the age of the universe to finish that many steps. #### Scaling Behavior The most useful question in practice is: **how does cost change if the input doubles?** | Class | Cost when input is $2\times$ | When input is $10\times$ | |---|---|---| | $O(1)$ | Unchanged | Unchanged | | $O(\log n)$ | Increases by a constant amount | Increases by a constant amount | | $O(n)$ | $2\times$ | $10\times$ | | $O(n \log n)$ | A little more than $2\times$ | A little more than $10\times$ | | $O(n^2)$ | $4\times$ | $100\times$ | | $O(n^3)$ | $8\times$ | $1000\times$ | | $O(2^n)$ | Gets squared | Meaningless | This table makes it possible to estimate without measuring. A quadratic operation that takes two seconds with a thousand records takes two hundred seconds with ten thousand. If the same job is done with a linearithmic algorithm, tenfold data brings roughly a thirteenfold increase. It is also used in reverse: an algorithm's class can be estimated by looking at how measured times change with input. If time quadruples when input doubles, there is quadratic behavior in the code. #### Sublinear Classes Classes like $O(\log n)$ and $O(\sqrt{n})$ produce a result **without reading all of the input**. This is possible only if the data is already organized: binary search assumes sortedness, a hash table assumes a table already built. For this reason, sublinear costs usually come together with a **preprocessing** cost. If an array is going to be sorted and then searched a thousand times, the $O(n \log n)$ sorting cost is divided across the thousand searches and pays for itself many times over. Sorting for a single search, on the other hand, makes no sense. This is the decision criterion: **once the preprocessing cost is divided by the number of queries, is there still a gain?** #### Why $n \log n$ Appears Often This class appears often for two reasons. The first is that it is the natural consequence of the **divide-and-conquer** structure: the problem is split in two at every step ($\log n$ depth), and all elements are processed at every level ($n$ work). Merge sort is the canonical example of this. The second is that it is the **lower bound** for comparison-based sorting: no comparison-based algorithm can be faster than this. This result will be proved in the searching and sorting topic. #### Exponential Classes and Combinatorial Explosion Exponential and factorial classes arise from solutions of the form "try every possibility": - All subsets of $n$ elements: $2^n$ of them. - All orderings of $n$ elements: $n!$ of them. ```python import math for n in (10, 20, 30, 50): print(n, f"2^n = {2**n:.3g}", f"n! = {math.factorial(n):.3g}") # 10 2^n = 1.02e+03 n! = 3.63e+06 # 20 2^n = 1.05e+06 n! = 2.43e+18 # 30 2^n = 1.07e+09 n! = 2.65e+32 # 50 2^n = 1.13e+15 n! = 3.04e+64 ``` With thirty elements, the number of subsets exceeds a billion; with twenty elements, the number of orderings reaches two quintillion. This shows why brute-force solutions can be used only on very small inputs. In such problems, three paths are followed: keeping the input small, narrowing the search space with intelligent pruning (backtracking from the Programming Fundamentals course), or giving up on an exact solution and producing an approximate result. The theoretical classification of these problems belongs to the **Theory of Computation** course. #### When Constants Matter Asymptotic notation eliminates constants, but constants exist in the real world and dominate at small inputs. When an algorithm costing $100n$ is compared to one costing $n^2$, the second is faster for $n < 100$. The crossover point is determined by the ratio of the constants. The practical consequence is seen in library implementations: sorting algorithms switch to insertion sort on small subarrays, because at those sizes the simple algorithm's small constant wins out. This kind of hybrid approach shows where asymptotic analysis ends and measurement begins. #### Summary - Classes are ordered from constant and logarithmic to exponential and factorial; the differences between them are of order at large inputs. - How cost changes when input doubles is the practical way to recognize a class. - Sublinear classes require data that is already organized; preprocessing cost is evaluated by dividing it across the number of queries. - $n \log n$ is both the natural consequence of the divide-and-conquer structure and the lower bound for comparison-based sorting. - Exponential and factorial classes arise from brute-force solutions and are practical only for very small inputs. - Constants dominate at small inputs; libraries therefore use hybrid approaches. #### Next Step The classes have been recognized; next comes **determining** which class a piece of code belongs to by looking at it. The next lesson will build, step by step, the methods for computing the cost of loops, recursion, and amortized operations. ### The Method for Computing Complexity Source: https://academia.sh/en/courses/algorithms/computing-complexity Counting cost with loop and conditional rules, recurrence relations, the master theorem, and amortized analysis. The classes have been recognized; next comes determining which class a piece of code belongs to by looking at it. This lesson gives the rules for the calculation. The rules are few and are applied in combination. #### Basic Rules **Sequential parts are added.** If two parts run one after the other, their costs are added, and the larger one dominates: $O(n) + O(n^2) = O(n^2)$. **A loop is body cost times iteration count.** A loop with a constant body that runs $n$ times is $O(n)$. **In nested loops, costs multiply.** Two loops, each running $n$ times, are $O(n^2)$. **In conditional structures, the worst branch is taken.** The guarantee is given over the worst case. **A constant number of repetitions is constant.** A loop whose iteration count does not depend on $n$ is $O(1)$. ```python def counting_examples(n: int) -> dict[str, int]: counters = {"single": 0, "nested": 0, "triangular": 0, "halving": 0} for i in range(n): # O(n) counters["single"] += 1 for i in range(n): # O(n²) for j in range(n): counters["nested"] += 1 for i in range(n): # O(n²) — triangular, but still quadratic for j in range(i): counters["triangular"] += 1 i = 1 while i < n: # O(log n) counters["halving"] += 1 i *= 2 return counters print(counting_examples(8)) # {'single': 8, 'nested': 64, 'triangular': 28, 'halving': 3} print(counting_examples(16)) # {'single': 16, 'nested': 256, 'triangular': 120, 'halving': 4} ``` When the input doubles, the counts change as the classes predict: single doubles, nested quadruples; the halving loop only increases by one. The triangular loop needs attention. The total iteration count is $n(n-1)/2$; once the constant factor is eliminated, $O(n^2)$ remains. The observation "it runs about half as many times" does not change the class — it only changes the constant. #### How the Loop Bound Changes The iteration count depends on how the loop variable advances: | Advancement | Iteration count | Class | |---|---|---| | `i += 1` | $n$ | $O(n)$ | | `i += k` | $n/k$ | $O(n)$ | | `i *= 2` | $\log_2 n$ | $O(\log n)$ | | `i = i * i` | $\log \log n$ | $O(\log \log n)$ | | `i -= 1` (from n) | $n$ | $O(n)$ | The second row matters: advancing by a constant step does not change the class. Multiplicative advancement does; this is the source of binary search's logarithmic behavior. #### Recurrence Relations A recursive algorithm's cost is written in terms of itself. This expression is called a **recurrence relation**. Three common patterns: $$ T(n) = T(n-1) + O(1) \implies T(n) = O(n) $$ At every step the problem shrinks by one element and constant work is done; a total of $n$ steps. Factorial computation is of this pattern. $$ T(n) = T(n/2) + O(1) \implies T(n) = O(\log n) $$ At every step the problem is halved and constant work is done; the number of halvings is $\log_2 n$. Binary search is of this pattern. $$ T(n) = 2\,T(n/2) + O(n) \implies T(n) = O(n \log n) $$ The problem is split into two halves, and all elements are processed at every level. Merge sort is of this pattern, and it is the main example of the next topic. #### Recursion Tree The intuitive way to solve a relation is to draw the calls as a tree and sum the cost level by level. For the relation $T(n) = 2T(n/2) + n$: | Level | Call count | Work per call | Level total | |---|---|---|---| | 0 | 1 | $n$ | $n$ | | 1 | 2 | $n/2$ | $n$ | | 2 | 4 | $n/4$ | $n$ | | $k$ | $2^k$ | $n/2^k$ | $n$ | Every level's total is $n$, and the number of levels is $\log_2 n$; the total comes out to $n \log n$. The same method gives a different result for $T(n) = 2T(n/2) + O(1)$: the level totals grow as $1, 2, 4, \dots, n$, and the total comes out to $O(n)$. The leaf count becomes dominant. #### The Master Theorem Most divide-and-conquer relations fit a single pattern: $$ T(n) = a\,T(n/b) + f(n) $$ Here $a$ is the number of subproblems, $b$ is the shrink factor, and $f(n)$ is the cost of splitting and combining. The result is determined by comparing $f(n)$ with $n^{\log_b a}$: - If $f(n)$ is smaller: $T(n) = \Theta(n^{\log_b a})$ — the leaves dominate. - If the two are of the same order: $T(n) = \Theta(n^{\log_b a} \log n)$ — all levels are equal. - If $f(n)$ is larger: $T(n) = \Theta(f(n))$ — the root dominates. In merge sort, $a = 2$, $b = 2$, $f(n) = n$; since $n^{\log_2 2} = n$, the second case applies, and the result comes out to $\Theta(n \log n)$. The theorem's full statement contains additional conditions, and not every relation fits this pattern; for those that do not, the tree method or a direct solution is used. #### Amortized Analysis The cost of some operations is misleading when looked at individually. The dynamic array from the Data Structures course was an example of this: appending is mostly constant, occasionally linear. The **aggregate method** computes the total cost of $m$ operations and divides by $m$. In a dynamic array, the total copying for $n$ appends was less than $2n$ — with capacity doubling, the copies sum as the geometric series $1 + 2 + 4 + \dots$; the amortized cost per append is constant. ```python def total_copies(n: int) -> int: """The total number of copies made over n appends (capacity doubling each time).""" capacity, length, copies = 1, 0, 0 for _ in range(n): if length == capacity: copies += length # every element is moved to the new block capacity *= 2 length += 1 return copies for n in (16, 1000, 100_000): print(n, total_copies(n), f"{total_copies(n)/n:.2f}") # 16 15 0.94 # 1000 1023 1.02 # 100000 131071 1.31 ``` The average number of copies per append stays around a small constant as the input grows; it does not grow linearly. The statement "amortized constant cost" says exactly this. There are two more methods. The **accounting method** charges every cheap operation a share for expensive work to come; the **potential method** expresses the structure's "stored energy" with a function. All three give the same result; the choice depends on which one makes the proof shorter. #### Order of Application The sequence followed to find the cost of a piece of code: 1. **Define the input size.** What does $n$ count? 2. **Find the innermost operation.** Which operation repeats most often? 3. **Multiply the iteration counts.** From outside to inside in nested structures. 4. **Add the sequential parts**, take the largest term. 5. **If there is recursion, write the relation** and solve it. 6. **If there is amortized behavior**, divide total cost by operation count. When the steps are applied in order, the result is obtained without resorting to intuition. #### Summary - Sequential parts are added, costs multiply in nested loops, and the worst branch is taken in conditionals. - Multiplicative advancement of the loop variable makes the iteration count logarithmic; advancing by a constant step does not change the class. - Recursive cost is written as a relation; three common patterns give linear, logarithmic, and linearithmic results. - The recursion tree solves the relation by summing cost level by level. - The master theorem classifies divide-and-conquer relations into three cases. - Amortized analysis divides the total cost of a sequence of operations by the operation count. #### Next Step So far, only time has been considered. Yet algorithms also use memory, and the two frequently substitute for one another: it is possible to run faster by using more memory, or slower by using less. The next lesson takes up this trade-off and its typical patterns. ### Time and Space Trade-off Source: https://academia.sh/en/courses/algorithms/time-and-space-trade-off Space complexity, in-place operation, the cost of the recursion stack, memoization and precomputation patterns, and the limits of the trade-off. So far, only a single resource has been counted: operation count. Yet algorithms also consume memory, and the two resources frequently substitute for one another. Doing fewer operations by using more memory, or the reverse, is possible for most problems. This lesson defines the second axis and shows the patterns of the trade-off between them. #### Space Complexity **Space complexity** is the rate at which the amount of memory used grows as a function of input size. The same notations used for time complexity apply. There are two separate quantities, and confusing them is a common error: **Total space** is all memory used, including the input. Every algorithm operating on an $n$-element array uses at least $O(n)$ total space. **Auxiliary space** is memory allocated beyond the input. This is what is meaningful in comparisons, because holding the input is already mandatory. Algorithms whose auxiliary space is constant are called **in-place**. The following function that reverses an array is in-place: no matter how many elements there are, it uses no more than three variables. ```python def reverse_in_place(array: list[int]) -> None: """Reverses the array in place. Auxiliary space: O(1).""" left, right = 0, len(array) - 1 while left < right: array[left], array[right] = array[right], array[left] left += 1 right -= 1 def reverse_copy(array: list[int]) -> list[int]: """Produces a new array. Auxiliary space: O(n).""" return [array[i] for i in range(len(array) - 1, -1, -1)] a = [1, 2, 3, 4, 5] reverse_in_place(a) print(a) # [5, 4, 3, 2, 1] print(reverse_copy([1, 2, 3, 4, 5])) # [5, 4, 3, 2, 1] ``` Both are $O(n)$ in time; the axis where they differ is space. The choice depends on whether the caller needs the original array and how constrained memory is. #### The Recursion Stack Consumes Space In a recursive solution, memory is used even if no array is explicitly allocated: every pending call holds a frame on the call stack introduced in the Programming Fundamentals course. The space cost is the number of calls at the **deepest point** — not the total number of calls. | Structure | Maximum depth | Auxiliary space | |---|---|---| | Linear recursion ($n$ steps) | $n$ | $O(n)$ | | Halving recursion | $\log n$ | $O(\log n)$ | | Tail recursion (if converted to a loop) | $1$ | $O(1)$ | The distinction has a practical consequence: on a million-element array, a linearly deep recursion exceeds the runtime's stack limit. The loop-based version of the same algorithm does not hit the limit. #### Classic Trade-off Patterns There are several established ways to convert memory into time. **Memoization.** Computed results are stored and not recomputed when requested again. Time decreases, space increases. **Precomputation.** Results are written into a table before a query arrives. Query cost drops to constant, and table space is paid for. **Indexing.** The hash table and trees from the Data Structures course lower search cost in exchange for extra structure. **Compression.** The reverse direction: space decreases, and encoding-decoding work increases time. The effect of memoization is seen most clearly in a recursion that does the same computation twice. ```python def fib_naive(n: int, counter: list[int]) -> int: counter[0] += 1 if n < 2: return n return fib_naive(n - 1, counter) + fib_naive(n - 2, counter) def fib_tabulated(n: int, counter: list[int], table: dict[int, int]) -> int: counter[0] += 1 if n < 2: return n if n not in table: table[n] = fib_tabulated(n - 1, counter, table) + fib_tabulated(n - 2, counter, table) return table[n] for n in (10, 20, 30): a, b = [0], [0] print(n, fib_naive(n, a), a[0], fib_tabulated(n, b, {}), b[0]) # 10 55 177 55 19 # 20 6765 21891 6765 39 # 30 832040 2692537 832040 59 ``` Call count drops from exponential to linear: for thirty, fifty-nine calls instead of two million seven hundred thousand. The price paid is a dictionary of $n$ entries — that is, $O(n)$ auxiliary space. #### Same Problem, Two Balance Points The trade-off becomes concrete by writing two solutions to a single problem. The problem: does an array contain two elements whose sum equals a given target? ```python def two_sum_hash(array: list[int], target: int) -> tuple[int, int] | None: """Time O(n), auxiliary space O(n).""" seen: dict[int, int] = {} for i, value in enumerate(array): if target - value in seen: return seen[target - value], i seen[value] = i return None def two_sum_two_pointer(array: list[int], target: int) -> tuple[int, int] | None: """On a sorted array, time O(n), auxiliary space O(1).""" left, right = 0, len(array) - 1 while left < right: total = array[left] + array[right] if total == target: return left, right if total < target: left += 1 else: right -= 1 return None print(two_sum_hash([8, 3, 11, 5, 2], 13)) # (0, 3) — 8 + 5 print(two_sum_two_pointer([2, 3, 5, 8, 11], 13)) # (0, 4) print(two_sum_hash([8, 3, 11, 5, 2], 100)) # None ``` The first solution works in a single pass on an unsorted array, but keeps a dictionary of $n$ entries. The second uses no auxiliary space at all, but in exchange requires the array to be sorted; if the sorting cost is added, the total becomes $O(n \log n)$. The choice is not the answer to "which is better"; it depends on which resource is constrained. If memory is plentiful and only a single query will be made, the first; if memory is tight or the array is already sorted, the second. #### The Trade-off Does Not Always Hold Two caveats prevent treating the trade-off as a mechanical rule. **Less space is sometimes faster.** Because of the memory hierarchy from the How Computers Work course, a small, contiguous structure fits in cache and can run faster than a large, scattered one. Here, reducing space reduces time as well. **Some improvements gain on both axes.** An idea that reduces a quadratic algorithm to linearithmic usually does not demand extra space either. The trade-off holds when the algorithm is held fixed — not when a better algorithm is found. For this reason, the order is to look first at improving the algorithm itself, and to resort to the trade-off only afterward. #### Decision Criterion In practice, the choice is made with three questions: 1. **Which resource is constrained?** Memory in an embedded system, time in batch processing. 2. **How many times will the result be used?** Precomputation is a loss for a one-off calculation; it pays for itself with many queries. 3. **How large will the input grow?** If space grows linearly, past a certain point the input no longer fits in memory and the solution becomes invalid. The third question is often skipped: a time overrun is a delay, but a memory overrun is the work stopping entirely. #### Summary - Space complexity is the rate at which memory usage grows relative to input; total space and auxiliary space are separate quantities. - Algorithms whose auxiliary space is constant are called in-place. - Recursion consumes as much stack space as the call count at the deepest point. - Memoization, precomputation, and indexing convert memory into time; compression works in the reverse direction. - Solutions to the same problem at different balance points are chosen according to which resource is constrained. - The trade-off holds while the algorithm is fixed; a better algorithm can gain on both axes. #### Next Step The tools of analysis are complete: cost has been defined, expressed with notation, computed, and split into two axes. The next topic will apply these tools for the first time to a serious family of algorithms — searching and sorting. Half a dozen solutions to the same problem will be compared with exactly these metrics. ## Searching and Sorting Linear and binary search, basic and advanced sorting algorithms, non-comparison methods, and selection criteria. ### Linear Search Source: https://academia.sh/en/courses/algorithms/linear-search Scanning unordered data, the expected comparison count for successful and unsuccessful search, the sentinel, and the justification of the linear lower bound. The analysis tools are ready; this topic applies them for the first time to a family of algorithms. Searching and sorting form suitable ground for this work, because they lend themselves to placing side by side solutions to the same problem at different costs. The simplest search is the starting point: walking the elements from start to end. #### The Algorithm and Its Correctness **Linear search** scans the array from start to end and returns the first position where it finds the sought value. ```python def linear_search(array: list[int], target: int) -> int: """The target's first position; -1 if not found. Invariant: at the start of every iteration, the target is not in the range 0..i-1. Termination: the number of remaining elements decreases by one every iteration. """ for i in range(len(array)): if array[i] == target: return i return -1 measurements = [5, 2, 9, 1, 5, 6] print(linear_search(measurements, 9)) # 2 print(linear_search(measurements, 5)) # 0 — first match print(linear_search(measurements, 7)) # -1 ``` Correctness is given by the two sentences in the docstring. The loop invariant, once the loop ends, becomes "the target is not in the range 0..n-1"; this justifies returning `-1`. The decreasing quantity is the termination guarantee. Two design decisions are made implicitly: if there are equal values, the **first** position is returned, and not-found is reported with a value that cannot be a valid index. #### The Cost of the Three Cases The measure is the number of comparisons. **Best case:** The target is the first element; 1 comparison, $O(1)$. **Worst case:** The target is the last element, or does not exist at all; $n$ comparisons, $O(n)$. **Average case:** Assuming the target is present in the array and every position is equally likely, the expected number of comparisons is $$ \frac{1 + 2 + \dots + n}{n} = \frac{n+1}{2} $$ which is also $O(n)$. In an unsuccessful search, $n$ comparisons are always made. ```python def comparison_count(array: list[int], target: int) -> int: for i in range(len(array)): if array[i] == target: return i + 1 return len(array) array = list(range(100)) total = sum(comparison_count(array, h) for h in array) print(total / len(array)) # 50.5 — (n+1)/2 print(comparison_count(array, -1)) # 100 — unsuccessful search ``` The average is roughly half the worst case. A constant-factor difference does not change the asymptotic class: both cases are linear. This shows when average-case analysis is meaningful — it determines the constant, not the class. #### The Sentinel The loop performs two tests every iteration: has the index bound been exceeded, and does the element equal the target. If the target is temporarily appended to the end of the array, the bound test becomes unnecessary; the search stops at that element at the latest. ```python def sentinel_search(array: list[int], target: int) -> int: array.append(target) # sentinel i = 0 while array[i] != target: i += 1 array.pop() return i if i < len(array) else -1 data = [5, 2, 9, 1, 5, 6] print(sentinel_search(data, 9), sentinel_search(data, 7), data) # 2 -1 [5, 2, 9, 1, 5, 6] ``` The gain is in the constant factor; the class is still $O(n)$. The method's cost is that it temporarily modifies the array — it cannot be used on shared data or in a multithreaded environment. This is a recurring lesson of the course: constant-factor improvements are real, but they do not substitute for an idea that changes the class. #### Why Nothing Better Is Possible The cost of search in an unordered array cannot be reduced, and the justification for this is an **adversary argument**. Suppose an algorithm does not look at all $n$ elements. There is at least one position it did not look at. When the algorithm says "not found", the adversary places the target at that position; since the algorithm's observations have not changed, neither does its answer, but the answer is now wrong. So every algorithm that works correctly must, in the worst case, look at every element: search in unordered data is $\Omega(n)$. Because linear search reaches this bound, it is **optimal** without any assumption of order. The only way to escape this bound is to change the assumption: keep the data sorted, or build an index structure. The next lesson follows the first route; the hash table from the Data Structures course follows the second. #### Access Distribution and the Effect of Ordering The average-case calculation assumed every element is searched for with equal probability. Real accesses are often not evenly distributed: a few records are searched for frequently, the rest rarely. With the probability of element $i$ being searched for equal to $p_i$, the expected number of comparisons is $$ \sum_{i=1}^{n} i \cdot p_i $$ This expression reaches its smallest value when the elements are arranged in **decreasing order of probability**. In other words, the array's order determines the cost, and the best static arrangement is ordering by frequency. ```python def expected_cost(probabilities: list[float]) -> float: return sum((i + 1) * p for i, p in enumerate(probabilities)) print(round(expected_cost([0.1, 0.2, 0.7]), 2)) # 2.6 — bad ordering print(round(expected_cost([0.7, 0.2, 0.1]), 2)) # 1.4 — ordered by frequency ``` If frequencies are not known in advance, heuristics that reorganize the list at run time are used: the found element is moved to the front, or advanced by one position. These do not change the worst case — the class is still $O(n)$ — but they noticeably lower the average under skewed distributions. #### Multiple Pieces of Information in One Pass A linear scan does not have to search only for a match; several quantities can be collected in the same pass. Searching for the minimum and the maximum separately requires $2n - 2$ comparisons; processing elements two at a time lowers the cost. ```python def min_and_max(array: list[int]) -> tuple[int, int, int]: """Returns (minimum, maximum, comparison count).""" n = len(array) if n % 2 == 0: low, high = min(array[0], array[1]), max(array[0], array[1]) i, count = 2, 1 else: low = high = array[0] i, count = 1, 0 while i < n - 1: a, b = array[i], array[i + 1] if a > b: a, b = b, a count += 3 # within-pair comparison + comparison with both ends low = min(low, a) high = max(high, b) i += 2 return low, high, count print(min_and_max([5, 2, 9, 1, 5, 6])) # (1, 9, 7) print(min_and_max(list(range(100)))) # (0, 99, 148) ``` For a hundred elements, 148 comparisons are made; searching separately would require 198. The general formula is $\lceil 3n/2 \rceil - 2$, and this is the known lower bound for the two extremes. The class is still $O(n)$. The gain matters when data comes from disk or the network and every pass is expensive: any information that can be collected in one pass is cheaper than a second pass. #### Summary - Linear search works on unordered data; its correctness is justified by the loop invariant and the decreasing quantity. - The best case is constant, the worst case is linear; the expected cost of a successful search is $(n+1)/2$ comparisons. - The sentinel removes the bound test; the gain is a constant factor, the class does not change. - The adversary argument shows that search in unordered data is $\Omega(n)$; linear search reaches this bound. - If access probabilities are not equal, ordering elements by decreasing frequency lowers the expected cost. - Collecting more than one quantity in a single pass reduces the number of passes and the total comparisons. #### Next Step The way to escape the linear lower bound is to build an assumption on the data. If the data is sorted, every comparison eliminates not just one element but half of them. The next lesson covers this idea — binary search — and the boundary conditions that are surprisingly difficult to write correctly. ### Binary Search Source: https://academia.sh/en/courses/algorithms/binary-search Halving in sorted data, boundary conditions justified by a loop invariant, variants that find the first position, and search over a monotone predicate. Linear search was optimal for unordered data. If the assumption changes, the bound changes too: if the array is sorted, a single comparison eliminates not one element but **half** of the remaining ones. This lesson works through that idea. The idea is simple; writing it correctly is not — binary search is known for having carried bugs in published implementations for decades. #### The Range Invariant The algorithm keeps a range where the target can be found, and halves that range on every iteration. The way to avoid boundary errors is to write down the meaning of the range from the very start. This lesson uses a **closed range**: both bounds of `[low, high]` are included in the range. ```python def binary_search(array: list[int], target: int) -> int: """A position of the target in the sorted array; -1 if not found. Invariant: if the target is in the array, it is within [low, high]. Termination: high - low decreases by at least one every iteration. """ low, high = 0, len(array) - 1 while low <= high: mid = low + (high - low) // 2 if array[mid] == target: return mid if array[mid] < target: low = mid + 1 else: high = mid - 1 return -1 sorted_array = [1, 3, 4, 7, 9, 11, 15, 20] print(binary_search(sorted_array, 9)) # 4 print(binary_search(sorted_array, 1)) # 0 print(binary_search(sorted_array, 20)) # 7 print(binary_search(sorted_array, 10)) # -1 ``` Three details carry the correctness of the implementation: **The loop condition `low <= high`.** Because the range is closed, a single-element range is also valid; writing `<` would leave the last element never tested. **Updating the bounds with `mid ± 1`.** The tested element is left outside the range. Writing `high = mid` may leave the range unshrunk and put the loop into an infinite state — the termination guarantee comes precisely from this step. **Computing the midpoint as `low + (high - low) // 2`.** Writing `(low + high) // 2` can overflow for large arrays in languages that use fixed-width integers. The overflow behavior from the How Computers Work course turns into a concrete bug here. #### Cost Every iteration halves the range and does constant work: $$ T(n) = T(n/2) + O(1) \implies T(n) = O(\log n) $$ The number of comparisons in the worst case is $\lfloor \log_2 n \rfloor + 1$. ```python from collections.abc import Sequence def counted_binary_search(array: Sequence[int], target: int) -> tuple[int, int]: low, high, count = 0, len(array) - 1, 0 while low <= high: mid = low + (high - low) // 2 count += 1 if array[mid] == target: return mid, count if array[mid] < target: low = mid + 1 else: high = mid - 1 return -1, count for n in (1_000, 1_000_000, 1_000_000_000): # range is indexable, so a billion-element array is tested without allocating memory even_numbers = range(0, 2 * n, 2) print(n, counted_binary_search(even_numbers, n + 1)[1]) # an odd number: not in the array # 1000 10 # 1000000 20 # 1000000000 30 ``` Thirty comparisons are enough for a billion-element array. Linear search does the same work with a billion comparisons — this is the concrete counterpart of the scale-growth table in the Reading Complexity Classes lesson. The space cost is $O(1)$. The same algorithm can also be written recursively, but in that case it uses $O(\log n)$ stack space. #### Lower Bound: Why Nothing Faster Exists Comparison-based search produces one of three outcomes at every step: less, equal, greater. If the algorithm's behavior is drawn as a decision tree, every leaf of the tree is a possible answer, and an array of $n$ elements has at least $n$ different answers. A binary tree of height $h$ can have at most $2^h$ leaves. From $2^h \geq n$ it follows that $h \geq \log_2 n$: comparison-based search is $\Omega(\log n)$. The same decision-tree idea will be reused for sorting's lower bound. #### First and Last Position If the array has repeated values, the implementation above returns **any** match. Many sorting-related operations, however, want the first match. The **lower bound** is the position of the first element not less than the target. If there is no match, it gives the position where the target could be inserted without breaking the order. ```python def lower_bound(array: list[int], target: int) -> int: """The smallest i satisfying array[i] >= target (len(array) if none). Invariant: the answer is within [low, high]; the range is kept half-open. """ low, high = 0, len(array) while low < high: mid = low + (high - low) // 2 if array[mid] < target: low = mid + 1 else: high = mid return low repeated = [1, 3, 3, 3, 7, 9, 9] print(lower_bound(repeated, 3)) # 1 — first 3 print(lower_bound(repeated, 9)) # 5 — first 9 print(lower_bound(repeated, 4)) # 4 — insertion point print(lower_bound(repeated, 10)) # 7 — end of the array ``` This variant uses a **half-open** range: `high` is not included in the range. This is why the loop condition is `low < high` and the update is `high = mid`. Mixing the two variants is the most common source of bugs in binary search — how the range is kept is chosen once, and every line is written accordingly. The upper bound finds the first element **greater** than the target; the difference between the two results gives how many times the target occurs in the array. #### Beyond the Sorted Array Binary search's real condition is not "the array is sorted" but something more general: the existence of a **monotone predicate**. If a condition is false up to a certain point and always true after it, that point can be found with binary search. ```python def integer_sqrt(n: int) -> int: """The largest k satisfying k*k <= n.""" low, high, answer = 0, n, 0 while low <= high: mid = low + (high - low) // 2 if mid * mid <= n: answer = mid low = mid + 1 else: high = mid - 1 return answer print(integer_sqrt(0), integer_sqrt(15), integer_sqrt(16), integer_sqrt(10**18)) # 0 3 4 1000000000 ``` There is no array here; what is being searched for is the last value at which the predicate `mid * mid <= n` stays true. Because the predicate is monotone, halving is valid. This generalization is a common design tool: problems of the form "smallest sufficient capacity" or "largest valid threshold" are solved directly with binary search over the range of candidate values. #### When Not to Use It Binary search rests on three assumptions, and it is not preferred once one of them breaks. **If sortedness does not come for free.** Sorting the array for a single search is $O(n \log n)$; linear search is $O(n)$. Sorting pays for itself only when there are many queries. **If there is no random access.** Reaching the middle element in a linked list is linear, and the logarithmic gain vanishes. The search trees from the Data Structures course fill exactly this gap. **If the data keeps changing.** Updating a sorted array on every insertion is $O(n)$; a balanced tree or a hash table is more suitable in this case. #### Summary - Binary search halves the range in sorted data; its correctness is justified by an invariant that keeps the meaning of the range fixed. - The closed and half-open range variants require different loop conditions and updates; the two must not be mixed. - Cost is $O(\log n)$, following from $T(n) = T(n/2) + O(1)$; space is $O(1)$. - The decision-tree argument shows that comparison-based search is $\Omega(\log n)$. - The lower-bound variant gives the first match or the insertion position. - The method applies to any problem that searches for the first value at which a monotone predicate becomes true. #### Next Step Binary search's condition was sortedness; so sorting itself must now be examined. The next lesson covers three basic sorting algorithms — bubble, selection, and insertion — along with their quadratic costs, their stability, and the points where they differ from one another. ### Bubble, Selection, and Insertion Sort Source: https://academia.sh/en/courses/algorithms/basic-sorts The definition of the sorting problem, the criteria of stability and in-place operation, the comparison and move costs of three quadratic algorithms, and the inversion count. Binary search assumed sortedness; so sorting itself must now be examined. Sorting stands at the center of algorithm education: the same problem has been solved dozens of times with different ideas, and the solutions have been compared with exactly the tools of this course. This lesson covers three basic algorithms with quadratic cost. The goal is not only to learn them, but to establish a baseline against which the better algorithms of the following lessons will be compared. #### The Problem and Its Criteria **The sorting problem:** The input is an array of comparable elements. The output is an array that is a **permutation** of the same elements, arranged in non-decreasing order. Both conditions are required. If only orderedness were demanded, deleting the input and returning an empty array would count as a "solution"; the permutation condition rules this out. Sorting algorithms are distinguished by three criteria: **Stability.** An algorithm is stable if it preserves the relative order of elements with equal keys. This is decisive in multi-key sorting: records first sorted by city, then by date with a stable algorithm, keep the city order intact. **In-place operation.** An algorithm is in-place if its extra space is constant. **Adaptivity.** An algorithm is adaptive if its cost drops when the input is partially sorted. Two separate costs are also counted: the number of **comparisons** and the number of **moves** (swaps or shifts). If the elements are large objects, moves are expensive; if comparison is a complex function, comparisons are expensive. #### Bubble Sort Adjacent elements are compared and swapped if out of order. On every pass, the largest element "bubbles" to the end. ```python def bubble_sort(array: list[int]) -> list[int]: """Invariant: after every outer iteration, the last `n - last` elements are in their final position.""" d = list(array) for last in range(len(d) - 1, 0, -1): swapped = False for i in range(last): if d[i] > d[i + 1]: d[i], d[i + 1] = d[i + 1], d[i] swapped = True if not swapped: # if no swap occurred, the array is sorted break return d print(bubble_sort([5, 2, 9, 1, 5, 6])) # [1, 2, 5, 5, 6, 9] ``` Without the early-exit flag, the algorithm makes $n(n-1)/2$ comparisons in every case. With the flag, it stops in a single pass on sorted input: the best case becomes $O(n)$. The worst and average cases are $O(n^2)$. The number of moves can also be quadratic — on reverse-sorted input, every comparison leads to a swap. The algorithm is stable (elements swap only when strictly out of order) and in-place. #### Selection Sort The minimum of the remaining segment is found, and it is swapped with the element at the start of the boundary. ```python def selection_sort(array: list[int]) -> list[int]: """Invariant: after every iteration, the first i elements are finally sorted.""" d = list(array) for i in range(len(d) - 1): smallest = i for j in range(i + 1, len(d)): if d[j] < d[smallest]: smallest = j d[i], d[smallest] = d[smallest], d[i] return d print(selection_sort([5, 2, 9, 1, 5, 6])) # [1, 2, 5, 5, 6, 9] ``` The number of comparisons is independent of the input: always $n(n-1)/2$. It is not adaptive — it pays the full cost even on sorted input. In exchange, the **number of moves is at most $n-1$**, and this is the algorithm's sole advantage: if elements are very large, or if writing is expensive (in some persistent storage types, the cost of reading and writing is unequal), an algorithm that writes little may be preferred. In this form it is **not** stable: swapping with a distant element can disturb the order of equal keys. ```python def selection_sort_records(records: list[tuple[int, str]]) -> list[tuple[int, str]]: """Sorts by the first field (the key) only; the second field is an identity.""" d = list(records) for i in range(len(d) - 1): smallest = i for j in range(i + 1, len(d)): if d[j][0] < d[smallest][0]: smallest = j d[i], d[smallest] = d[smallest], d[i] return d print(selection_sort_records([(2, "a"), (2, "b"), (1, "c")])) # [(1, 'c'), (2, 'b'), (2, 'a')] ``` In the output, `b` has moved ahead of `a`; in the input the order was reversed. A variant that shifts instead of swapping would be stable, but then the move advantage is lost. #### Insertion Sort Every element is inserted by shifting it to its correct place within the sorted segment before it. This is the way playing cards are sorted by hand. ```python def insertion_sort(array: list[int]) -> list[int]: """Invariant: at the start of every iteration, the first i elements are sorted among themselves.""" d = list(array) for i in range(1, len(d)): key = d[i] j = i - 1 while j >= 0 and d[j] > key: d[j + 1] = d[j] # shift j -= 1 d[j + 1] = key return d def insertion_sort_records(records: list[tuple[int, str]]) -> list[tuple[int, str]]: d = list(records) for i in range(1, len(d)): key = d[i] j = i - 1 while j >= 0 and d[j][0] > key[0]: d[j + 1] = d[j] j -= 1 d[j + 1] = key return d print(insertion_sort([5, 2, 9, 1, 5, 6])) # [1, 2, 5, 5, 6, 9] print(insertion_sort_records([(2, "a"), (2, "b"), (1, "c")])) # [(1, 'c'), (2, 'a'), (2, 'b')] — the a, b order from the input is preserved ``` The `>` sign in the loop condition is the source of stability: on equality, shifting stops, and the new element settles right after its equal. Writing `>=` would make the algorithm lose its stability. The best case is sorted input: the inner loop never runs, cost is $O(n)$. The worst case is reverse-sorted input: $n(n-1)/2$ shifts, $O(n^2)$. In the average case, every element shifts about half the length of the sorted segment; still quadratic, but with a smaller constant. #### The Inversion Count Insertion sort's cost can be measured exactly by how "disordered" the input is. An **inversion** is a pair where $i < j$ but $d_i > d_j$. A sorted array has zero, a reverse-sorted array has $n(n-1)/2$. Every shift insertion sort performs eliminates exactly one inversion; therefore the total number of shifts equals the number of inversions, and the cost is $O(n + \text{inversions})$. ```python def inversion_count(array: list[int]) -> int: return sum(1 for i in range(len(array)) for j in range(i + 1, len(array)) if array[i] > array[j]) def insertion_shift_count(array: list[int]) -> int: d, count = list(array), 0 for i in range(1, len(d)): key, j = d[i], i - 1 while j >= 0 and d[j] > key: d[j + 1] = d[j] j -= 1 count += 1 d[j + 1] = key return count for example in ([1, 2, 3, 4, 5], [5, 2, 9, 1, 5, 6], [5, 4, 3, 2, 1]): print(example, inversion_count(example), insertion_shift_count(example)) # [1, 2, 3, 4, 5] 0 0 # [5, 2, 9, 1, 5, 6] 6 6 # [5, 4, 3, 2, 1] 10 10 ``` The two columns being equal in every row is not a coincidence; it is the exact definition of what the algorithm does. The result matters in practice: on **nearly sorted** data, insertion sort runs close to linear. An array formed by adding a few new records to an already sorted log fits this description. #### Comparison | Criterion | Bubble | Selection | Insertion | |---|---|---|---| | Best case | $O(n)$ (with flag) | $O(n^2)$ | $O(n)$ | | Average / worst | $O(n^2)$ | $O(n^2)$ | $O(n^2)$ | | Move count | $O(n^2)$ | $O(n)$ | $O(n^2)$ | | Stable | Yes | No | Yes | | In-place | Yes | Yes | Yes | | Adaptive | Yes | No | Yes | All three are in the quadratic class; the difference between them is in constants and secondary criteria. In practice, insertion sort stands out on small arrays and nearly sorted data — which is why advanced sorting implementations switch to it for small segments. Bubble sort has no clear advantage; its instructional value is that it is the plainest form of the adjacent-swap idea. #### Summary - The sorting problem requires two conditions: the output must be ordered, and it must be a permutation of the input. - Algorithms are distinguished by stability, in-place operation, and adaptivity; comparisons and moves are counted separately. - Bubble sort works by adjacent swaps; an early-exit flag brings the best case down to linear. - Selection sort always makes quadratic comparisons but a linear number of moves; in this form it is not stable. - Insertion sort is stable, in-place, and adaptive; its shift count equals the inversion count. - All three are in the quadratic class; the difference is in constants and secondary criteria. #### Next Step As the scale-growth table showed, the quadratic class could not be used on data in the millions. The next lesson applies the divide-and-conquer idea, whose recurrence was solved in the complexity calculation lesson, to sorting: merge sort delivers an $O(n \log n)$ guarantee together with stability. ### Merge Sort Source: https://academia.sh/en/courses/algorithms/merge-sort Stable sorting with divide and conquer, the correctness of the merge operation, the bottom-up variant, external sorting, and counting inversions. Quadratic algorithms cannot be used on data in the millions. The recurrence solved in the Method for Computing Complexity lesson already pointed to the way out: $$ T(n) = 2\,T(n/2) + O(n) \implies T(n) = O(n \log n) $$ This lesson builds the algorithm that produces that recurrence: split the array in two, sort each half, merge the two sorted halves. #### The Merge The algorithm's core is **merging two sorted arrays into one sorted array**. Two pointers are used; the smaller one is taken at every step. ```python def merge(left: list[int], right: list[int]) -> list[int]: """Merges two sorted arrays into one sorted array. Invariant: the result is the sorted form of the elements taken from the two arrays so far, and every element not yet taken is not less than every element already in the result. """ result: list[int] = [] i = j = 0 while i < len(left) and j < len(right): if left[i] <= right[j]: # left takes priority on equality: stability result.append(left[i]) i += 1 else: result.append(right[j]) j += 1 result.extend(left[i:]) # once one is exhausted, the remainder of the other is appended result.extend(right[j:]) return result print(merge([1, 5, 9], [2, 5, 6])) # [1, 2, 5, 5, 6, 9] ``` The merge is $O(n)$: every element is taken exactly once and never looked at again. The `<=` sign is the source of stability. On equality, the element on the left — the one that came first in the input — is chosen. Writing `<` would make the algorithm lose its stability; this is one of the examples where a one-character difference determines a behavioral property. #### Divide and Conquer What remains is only the recursive frame. ```python def merge_sort(array: list[int]) -> list[int]: if len(array) <= 1: # base case: zero or one element is already sorted return list(array) mid = len(array) // 2 left = merge_sort(array[:mid]) right = merge_sort(array[mid:]) return merge(left, right) print(merge_sort([5, 2, 9, 1, 5, 6])) # [1, 2, 5, 5, 6, 9] print(merge_sort([])) # [] print(merge_sort([3, 3, 3])) # [3, 3, 3] ``` Its correctness is justified by induction: the base case is correct; if both halves are correctly sorted, the merge operation also produces a correctly sorted array. Termination comes from the subproblems shrinking with certainty — the `mid` computation ensures neither part is empty. #### Cost At every level of the recursion tree, a total of $n$ units of merge work are done, and the number of levels is $\log_2 n$. Because the split is made without looking at the input's content, this is the same **in every case**: | Case | Comparisons | Class | |---|---|---| | Best | $\sim \frac{n \log_2 n}{2}$ | $\Theta(n \log n)$ | | Average | $\sim n \log_2 n$ | $\Theta(n \log n)$ | | Worst | $\sim n \log_2 n$ | $\Theta(n \log n)$ | The same cost regardless of the input — this guarantee is a property the quicksort of the next lesson does not have. Space cost is the algorithm's weak point: the merge uses an $O(n)$ extra array for the result. Added to this is the recursion stack's $O(\log n)$ depth. In-place merge variants working on the array exist, but their constants are large and they complicate the code. ```python def counted_sort(array: list[int]) -> tuple[list[int], int]: """(sorted array, comparison count)""" if len(array) <= 1: return list(array), 0 mid = len(array) // 2 left, a = counted_sort(array[:mid]) right, b = counted_sort(array[mid:]) result: list[int] = [] i = j = count = 0 while i < len(left) and j < len(right): count += 1 if left[i] <= right[j]: result.append(left[i]); i += 1 else: result.append(right[j]); j += 1 result.extend(left[i:]); result.extend(right[j:]) return result, a + b + count import math for n in (16, 1024, 65_536): data = [(i * 7919) % n for i in range(n)] # regular but unsorted input print(n, counted_sort(data)[1], int(n * math.log2(n))) # 16 35 64 # 1024 8929 10240 # 65536 956515 1048576 ``` The measured comparison count stays below the $n \log_2 n$ estimate; because when one array in a merge is exhausted early, the remaining elements are transferred without comparison, the actual count falls slightly under the bound. The order of magnitude is the same. #### The Bottom-Up Variant The same algorithm can be written without recursion: single-element blocks are merged two at a time first, then pairs, then groups of four. ```python def bottom_up_merge_sort(array: list[int]) -> list[int]: d = list(array) width = 1 while width < len(d): for start in range(0, len(d), 2 * width): mid = min(start + width, len(d)) end = min(start + 2 * width, len(d)) d[start:end] = merge(d[start:mid], d[mid:end]) width *= 2 return d print(bottom_up_merge_sort([5, 2, 9, 1, 5, 6])) # [1, 2, 5, 5, 6, 9] print(bottom_up_merge_sort([4, 3, 2, 1])) # [1, 2, 3, 4] ``` The result is the same, and no stack space is spent. An adaptive variant, instead of single-element blocks, treats the **runs** already sorted in the input as the starting blocks; this reduces the number of levels on nearly sorted data. #### Working with Sequential Access The merge accesses elements from start to end in a single direction; it does not require random access. This property is decisive in two areas. **In linked lists.** Reaching the middle element in the linked list from the Data Structures course is linear, but the merge is done just by redirecting links. This is the sort preferred in practice for linked lists, and it requires no extra array. **In external sorting.** If the data does not fit in memory, chunks are loaded into memory one at a time, sorted, and written to disk, and the sorted chunks are then merged as a stream. Because the merge reads in a single direction, it makes sequential reading over disk or network possible — a direct consequence of the locality principle from the How Computers Work course. #### Counting Inversions In the previous lesson, the inversion count was computed by brute force in $O(n^2)$. During a merge, every time an element from the right is taken ahead of one from the left, it forms an inversion with **every remaining element on the left**; this observation brings the count down to $O(n \log n)$. ```python def fast_inversion_count(array: list[int]) -> tuple[list[int], int]: if len(array) <= 1: return list(array), 0 mid = len(array) // 2 left, a = fast_inversion_count(array[:mid]) right, b = fast_inversion_count(array[mid:]) result: list[int] = [] i = j = count = 0 while i < len(left) and j < len(right): if left[i] <= right[j]: result.append(left[i]); i += 1 else: result.append(right[j]); j += 1 count += len(left) - i # all remaining elements on the left form an inversion result.extend(left[i:]); result.extend(right[j:]) return result, a + b + count print(fast_inversion_count([5, 2, 9, 1, 5, 6])[1]) # 6 print(fast_inversion_count([5, 4, 3, 2, 1])[1]) # 10 print(fast_inversion_count(list(range(1000)))[1]) # 0 ``` The results are the same as the brute-force count. This is the first example of the divide-and-conquer idea being used beyond sorting: a small addition to the merge step computes an entirely different quantity. #### Summary - Merge sort splits the array in two, sorts the halves, and merges the sorted halves at linear cost. - Choosing the left element on equality during the merge provides stability. - Cost is $\Theta(n \log n)$ in every case; the split does not depend on the input's content. - Extra space is $O(n)$; this is the algorithm's main cost. - The bottom-up variant removes the recursion stack; the run-based variant adds adaptivity. - Because it works with sequential access, it is preferred for linked lists and external sorting. #### Next Step Merge sort is safe but requires extra space. The next lesson covers quicksort, which achieves the same linearithmic order while operating in place — at the cost of losing the worst-case guarantee. How pivot selection turns this loss into a matter of probability will be at the center of the lesson. ### Quicksort Source: https://academia.sh/en/courses/algorithms/quicksort In-place sorting with partitioning, the effect of pivot choice on the average and worst case, three-way partitioning, and selecting the kth element. Merge sort did its work in the merge step: splitting was cheap, merging was expensive. Quicksort reverses this — **splitting is expensive, and there is no merge**. The idea is this: an element is chosen (the pivot), and the array is split in two — those smaller than it and those larger. The pivot is now in its final position; the two parts are sorted independently, and because they already sit side by side, no additional operation is needed. #### Partitioning Partitioning chooses the last element as the pivot and splits the array into two regions in a single pass. ```python def partition(d: list[int], start: int, end: int) -> int: """Partitions the range d[start..end] by the pivot, returns the pivot's final position. Invariant: d[start..i] is less than or equal to the pivot, d[i+1..j-1] is greater than the pivot. """ pivot = d[end] i = start - 1 for j in range(start, end): if d[j] <= pivot: i += 1 d[i], d[j] = d[j], d[i] d[i + 1], d[end] = d[end], d[i + 1] return i + 1 example = [5, 2, 9, 1, 5, 6] k = partition(example, 0, len(example) - 1) print(k, example) # 4 [5, 2, 1, 5, 6, 9] ``` The pivot value is 6; by the end of the operation it settles at index 4. No element larger than it remains to its left, and none smaller remains to its right. Partitioning uses $O(n)$ time and $O(1)$ extra space. This is **Lomuto** partitioning; its code is short. **Hoare** partitioning advances from both ends toward the middle, performs fewer swaps, and is preferred in practice; in exchange, its boundary conditions are more delicate and it does not return the pivot's exact position. #### The Recursive Frame ```python def quicksort(array: list[int]) -> list[int]: d = list(array) def sort(start: int, end: int) -> None: if start >= end: # base case: zero or one element return k = partition(d, start, end) sort(start, k - 1) sort(k + 1, end) # the pivot (k) is in place; not reprocessed sort(0, len(d) - 1) return d print(quicksort([5, 2, 9, 1, 5, 6])) # [1, 2, 5, 5, 6, 9] print(quicksort([]), quicksort([4])) # [] [4] ``` Correctness comes from induction: after partitioning, the pivot is in its final position, and the two parts are independent of each other; if the parts are sorted correctly, the whole array is sorted. The algorithm is **in-place** — the only extra space is the recursion stack — and **not stable**: swapping with distant elements disturbs the order of equal keys. #### Cost and Pivot Choice Cost depends on how balanced the partitioning is. **Balanced split.** If the pivot lands in the middle every time, the recurrence is $T(n) = 2T(n/2) + O(n)$, and the result is $\Theta(n \log n)$. **Unbalanced split.** If the pivot is the smallest or largest element every time, one part stays empty: $T(n) = T(n-1) + O(n)$, that is, $\Theta(n^2)$. The second case is not merely theoretical. The implementation above, which chooses the last element as pivot, shows exactly this behavior on an **already sorted** array. ```python def partition_count(array: list[int]) -> int: """Total number of partitioning comparisons.""" d, total = list(array), 0 def sort(start: int, end: int) -> None: nonlocal total if start >= end: return total += end - start k = partition(d, start, end) sort(start, k - 1) sort(k + 1, end) sort(0, len(d) - 1) return total n = 500 print(partition_count(list(range(n)))) # 124750 — sorted: quadratic print(partition_count([(i * 7919) % n for i in range(n)])) # 5322 — balanced input ``` On sorted input, the number of comparisons is exactly equal to $n(n-1)/2$. On balanced input of the same size, the count drops by more than a factor of twenty. The solution is to choose the pivot more carefully: | Choice | Input that triggers the worst case | |---|---| | First or last element | Sorted or reverse-sorted array | | Middle element | A specially constructed array | | Median of three (first, middle, last) | A specially constructed array | | Random element | None — no input determines it | The first three are deterministic; a sufficiently informed adversary can always produce input that drives the algorithm into the quadratic case. With a random pivot, however, which element of the input will be chosen is not known, so the expected cost is $O(n \log n)$, and this rests on randomness, not on the input. The reason the expected cost is linearithmic is that splits are **usually reasonable**: a random pivot falls into the middle half with probability about $1/2$, and such a split shrinks the problem size by at least three-quarters. Shrinking by a constant factor with constant probability means logarithmic depth. Stack depth can also be controlled: if the **smaller** part is recursed into first and the larger part is handled with a loop, stack depth stays $O(\log n)$ even in the worst case. #### Repeated Keys If the array consists entirely of the same value, Lomuto partitioning puts every element into the less-than-or-equal region, and the split becomes unbalanced again. The solution is to split the array into **three** regions: smaller, equal, larger. ```python def three_way_sort(array: list[int]) -> list[int]: if len(array) <= 1: return list(array) pivot = array[len(array) // 2] smaller = [x for x in array if x < pivot] equal = [x for x in array if x == pivot] larger = [x for x in array if x > pivot] return three_way_sort(smaller) + equal + three_way_sort(larger) print(three_way_sort([5, 2, 9, 1, 5, 6])) # [1, 2, 5, 5, 6, 9] print(three_way_sort([3, 3, 3, 3, 3])) # [3, 3, 3, 3, 3] ``` The equal region is never processed again; on arrays with only a few distinct values, the cost approaches linear. The code here produces new lists for readability; an in-place three-way partitioning applies the same idea without extra space. #### The Selection Problem Partitioning's second use is finding the **kth smallest** element without sorting the whole array. Since the pivot's position is known after partitioning, the sought element can only be on one side; the other side is never processed. ```python def quickselect(array: list[int], k: int) -> int: """The kth smallest element (k starts from zero).""" d = list(array) start, end = 0, len(d) - 1 while True: if start == end: return d[start] p = partition(d, start, end) if p == k: return d[p] if k < p: end = p - 1 else: start = p + 1 data = [5, 2, 9, 1, 5, 6] print(quickselect(data, 0), quickselect(data, 3), quickselect(data, 5)) # 1 5 9 print(sorted(data)[3]) # 5 ``` The expected cost is $O(n)$: the problem size shrinks by a constant factor at every step, and the costs sum as $n + n/2 + n/4 + \dots < 2n$. Sorting and then reading the kth element would be $O(n \log n)$. The same problem also has a solution whose worst case is linear too ("median of medians"), but its constant is large, and in practice random-pivot selection is preferred. #### Summary - Quicksort partitions by a pivot and requires no merge step; it operates in place and is not stable. - Partitioning uses $O(n)$ time and $O(1)$ extra space; the pivot settles into its final position. - Cost is $\Theta(n \log n)$ on a balanced split, $\Theta(n^2)$ on an unbalanced split. - Deterministic pivot choices can be triggered by quadratic input; a random pivot makes the expected cost independent of the input. - Three-way partitioning lowers the cost on repeated keys. - The same partitioning finds the kth element at expected linear cost. #### Next Step Quicksort operates in place but has no worst-case guarantee; merge sort has the guarantee but needs extra space. The next lesson covers a third path that combines the two: heap sort, using the heap structure from the Data Structures course, operates in place and gives $O(n \log n)$ in every case. ### Heap Sort Source: https://academia.sh/en/courses/algorithms/heap-sort A binary heap on an array, sift-down, linear-time heap construction, guaranteed in-place linearithmic sorting, and the top-k elements. Two options were on hand: merge sort, guaranteed in every case but needing $O(n)$ extra space, or quicksort, operating in place but with a quadratic worst case. A third path delivers both good properties at once. The tool is the **binary heap**, introduced in the Data Structures course. #### The Heap as an Array A heap is a complete binary tree, and because it is complete, it can be held in an array without pointers. For node `i`: - Left child: `2i + 1` - Right child: `2i + 2` - Parent: `(i - 1) // 2` The **max-heap property** is that every node is not smaller than its children. The root is the array's largest element. The operation that restores the property when it is broken is **sift-down**: a node descends, swapping with the larger of its children, until it finds its place. ```python def sift_down(d: list[int], root: int, limit: int) -> None: """Sinks the node d[root] into place within the heap d[0..limit). Invariant: every node other than root satisfies the heap property. Termination: root increases by at least one level every iteration. """ while True: largest = root left, right = 2 * root + 1, 2 * root + 2 if left < limit and d[left] > d[largest]: largest = left if right < limit and d[right] > d[largest]: largest = right if largest == root: return d[root], d[largest] = d[largest], d[root] root = largest ``` Cost is bounded by the number of levels the node can descend: $O(\log n)$. #### Building a Heap Is Linear The way to turn an unordered array into a heap is to sift the non-leaf nodes **from the end toward the start**. Leaves are already valid heaps on their own, so the process starts from the middle. ```python def build_heap(d: list[int]) -> None: for i in range(len(d) // 2 - 1, -1, -1): sift_down(d, i, len(d)) example = [5, 2, 9, 1, 5, 6] build_heap(example) print(example) # [9, 5, 6, 1, 2, 5] ``` A superficial look assigns $O(\log n)$ to each of the $n$ nodes, estimating $O(n \log n)$. The actual cost is lower, because most nodes traverse **short** paths: nodes near the leaves are the majority, and they descend little. The number of nodes at height $h$ is at most $n / 2^{h+1}$, and each descends at most $h$ steps: $$ \sum_{h=0}^{\log n} \frac{n}{2^{h+1}} \cdot h \;\leq\; n \sum_{h=0}^{\infty} \frac{h}{2^{h+1}} = n $$ The total is $O(n)$ — building a heap is cheaper than inserting elements one at a time ($O(n \log n)$). ```python def build_steps(d: list[int]) -> int: count = 0 def sift(root: int, limit: int) -> None: nonlocal count while True: largest, left, right = root, 2 * root + 1, 2 * root + 2 if left < limit and d[left] > d[largest]: largest = left if right < limit and d[right] > d[largest]: largest = right if largest == root: return d[root], d[largest] = d[largest], d[root] count += 1 root = largest for i in range(len(d) // 2 - 1, -1, -1): sift(i, len(d)) return count for n in (1_000, 10_000, 100_000): data = [(i * 7919) % n for i in range(n)] print(n, build_steps(data)) # 1000 706 # 10000 7529 # 100000 71808 ``` The number of swaps stays directly proportional to $n$ — about $0.72n$ in all three measurements. If it were $n \log_2 n$, it would exceed a million and a half for a hundred thousand elements. #### Sorting Once the heap is built, sorting is simple: the root (the largest) is moved to the end of the array, the heap's limit is shrunk by one, and the new root is sifted. ```python def heap_sort(array: list[int]) -> list[int]: d = list(array) build_heap(d) for limit in range(len(d) - 1, 0, -1): d[0], d[limit] = d[limit], d[0] # put the largest in place sift_down(d, 0, limit) # repair the remaining section return d print(heap_sort([5, 2, 9, 1, 5, 6])) # [1, 2, 5, 5, 6, 9] print(heap_sort([3, 3, 3])) # [3, 3, 3] print(heap_sort([])) # [] ``` The invariant is this: after every iteration, the right end of the array is finally sorted, and the left section is a valid heap. Cost: building is $O(n)$, followed by $n-1$ sifts at $O(\log n)$ each; the total is $\Theta(n \log n)$ — **in every case**. There is a worst-case guarantee, and extra space is $O(1)$; the algorithm operates in place. It is not stable: swapping the root with the element at the end disturbs the order of equal keys. #### Comparing the Three Algorithms | Criterion | Merge | Quick | Heap | |---|---|---|---| | Worst case | $\Theta(n \log n)$ | $\Theta(n^2)$ | $\Theta(n \log n)$ | | Average | $\Theta(n \log n)$ | $\Theta(n \log n)$ | $\Theta(n \log n)$ | | Extra space | $O(n)$ | $O(\log n)$ stack | $O(1)$ | | Stable | Yes | No | No | | Memory access | Sequential | Mostly local | Scattered | The last row explains why heap sort, despite having the best guarantees, is not always the first choice in practice. Sifting walks the array with `2i + 1` jumps; the cache-line reasoning from the How Computers Work course works against it here. Quicksort's partitioning, by contrast, reads the array sequentially from start to end. This observation gives rise to a common hybrid design: start with quicksort; if recursion depth exceeds a threshold (meaning the splits are becoming unbalanced), switch to heap sort; and leave small segments to insertion sort. The result combines quicksort's practical speed with heap sort's worst-case guarantee. #### The Top k Elements The heap's main use outside of sorting is the **priority queue**; the application closest to sorting is finding the largest $k$ elements without sorting all the data. The method is to keep a **minimum** heap of size $k$: if a new element is larger than the heap's root, the root is discarded and the new one enters. ```python import heapq def largest_k(data: list[int], k: int) -> list[int]: """Returns the largest k elements in increasing order. Cost O(n log k).""" heap: list[int] = [] for value in data: if len(heap) < k: heapq.heappush(heap, value) elif value > heap[0]: heapq.heapreplace(heap, value) return sorted(heap) data = [(i * 7919) % 1000 for i in range(1000)] print(largest_k(data, 5)) # [995, 996, 997, 998, 999] print(largest_k([5, 2, 9, 1, 5, 6], 3)) # [5, 6, 9] ``` The cost is $O(n \log k)$; if $k$ is small, this is noticeably cheaper than sorting's $O(n \log n)$. Extra space is $O(k)$ — if the data comes from a stream and does not fit entirely into memory, this is the only workable route. #### Summary - A heap, a complete binary tree, is held in an array without pointers; child and parent indices are found by arithmetic. - Sift-down is $O(\log n)$; building a heap by sifting non-leaf nodes from the end toward the start is $O(n)$. - Heap sort moves the root to the end and shrinks the limit; it is $\Theta(n \log n)$ in every case and operates in place. - It is not stable, and because it accesses memory in a scattered pattern, its constant is larger than quicksort's. - Hybrid designs combine quicksort's speed with heap sort's guarantee. - A heap of size $k$ gives the largest $k$ elements at $O(n \log k)$ cost and $O(k)$ space. #### Next Step All three algorithms hit the linearithmic bound; this is not a coincidence but the lower bound of comparison-based sorting. The next lesson first proves this lower bound, then shows **how it can be surpassed**: sorts that do not compare elements but place them directly into their positions. ### Non-Comparison Sorts Source: https://academia.sh/en/courses/algorithms/non-comparison-sorts The decision-tree lower bound for comparison-based sorting; the assumptions, costs, and limits of counting, bucket, and radix sort. Three different ideas — merging, partitioning, heaping — arrived at the same bound: $\Theta(n \log n)$. This is not a coincidence. This lesson first proves why the bound cannot be surpassed, then shows how it can be surpassed by removing the proof's **assumption**. #### Proof of the Lower Bound A comparison-based sorting algorithm looks not at the elements' values but only at the outcomes of comparisons. Such an algorithm's behavior can be drawn as a **decision tree**: every internal node is a comparison, every branch is one of the outcomes, every leaf is a produced permutation. If the algorithm is correct, it must correctly sort **every** possible arrangement of the $n$ elements; so the tree has at least $n!$ leaves. The worst-case number of comparisons is the tree's height, and a binary tree of height $h$ has at most $2^h$ leaves: $$ 2^h \geq n! \implies h \geq \log_2(n!) = \Omega(n \log n) $$ The last equality follows from the fact that at least half of $n!$'s factors are greater than $n/2$: $n! \geq (n/2)^{n/2}$, that is, $\log_2(n!) \geq \frac{n}{2}\log_2\frac{n}{2}$. ```python import math for n in (10, 100, 1_000, 10_000): print(n, round(math.log2(math.factorial(n))), round(n * math.log2(n))) # 10 22 33 # 100 525 664 # 1000 8529 9966 # 10000 118458 132877 ``` The lower bound and the upper bound are of the same order; merge sort is only a small factor away from the bound. Any improvement to be made in comparison-based sorting is limited to a constant. The proof rests on a single assumption: **the algorithm only compares.** If the structure of the keys is used, the proof no longer applies. #### Counting Sort Assumption: the keys are integers between $0$ and $k-1$. How many times each value occurs is counted, the counts are turned into a cumulative sum, and elements are written directly into their final positions. ```python def counting_sort(array: list[int], k: int) -> list[int]: """Keys are in the range 0..k-1. Cost O(n + k), stable.""" counts = [0] * k for value in array: counts[value] += 1 for i in range(1, k): # cumulative sum: end positions counts[i] += counts[i - 1] result = [0] * len(array) for value in reversed(array): # going from end to start preserves stability counts[value] -= 1 result[counts[value]] = value return result print(counting_sort([5, 2, 9, 1, 5, 6], 10)) # [1, 2, 5, 5, 6, 9] print(counting_sort([3, 0, 3, 0], 4)) # [0, 0, 3, 3] ``` Cost is $O(n + k)$, extra space is $O(n + k)$. No comparison is made; every element finds its position by arithmetic. Traversing in reverse order is not a detail: it is exactly what provides stability. Among elements with equal keys, the one that comes last settles into the cumulative counter's last position, and relative order is preserved. This is invisible in the numbers themselves; it becomes decisive in uses where the key is part of a larger record. The method's limit lies in $k$: if the value range is much larger than the element count ($k \gg n$), cost and memory are determined by $k$. Sorting 32-bit integers with counting sort would require a count array of four billion entries. #### Bucket Sort Assumption: the keys lie in a known range and are **approximately uniformly** distributed. The range is divided into equal parts, every element is dropped into its own bucket, the buckets are sorted internally, and they are concatenated in order. ```python def bucket_sort(array: list[float], bucket_count: int) -> list[float]: """For values in the range 0 <= x < 1. Expected cost O(n) under uniform distribution.""" if not array: return [] buckets: list[list[float]] = [[] for _ in range(bucket_count)] for value in array: buckets[int(value * bucket_count)].append(value) result: list[float] = [] for bucket in buckets: bucket.sort() # small bucket: insertion sort would work too result.extend(bucket) return result print(bucket_sort([0.42, 0.11, 0.95, 0.47, 0.03], 5)) # [0.03, 0.11, 0.42, 0.47, 0.95] ``` Under uniform distribution, every bucket receives $n / \text{bucket count}$ elements on average; if the bucket count is chosen proportional to $n$, the sorts within buckets have constant cost, and the expected total is $O(n)$. When the assumption breaks, so does the guarantee: if all the elements fall into a single bucket, cost falls back to that of the algorithm used within the bucket — typically $O(n \log n)$ or $O(n^2)$. This is an example of the "linear" claim depending on the data. #### Radix Sort Assumption: the keys are made up of a fixed number of **digits**. Elements are sorted digit by digit. It starts from the least significant digit, and a **stable** sort is used at every digit; stability ensures the order established by the previous digits is preserved. ```python def radix_sort(array: list[int], base: int = 10) -> list[int]: """For non-negative integers. Cost O(d * (n + base)).""" if not array: return [] result = list(array) divisor = 1 while max(result) // divisor > 0: buckets: list[list[int]] = [[] for _ in range(base)] for value in result: buckets[(value // divisor) % base].append(value) result = [value for bucket in buckets for value in bucket] divisor *= base return result print(radix_sort([170, 45, 75, 90, 2, 802, 24, 66])) # [2, 24, 45, 66, 75, 90, 170, 802] print(radix_sort([5, 2, 9, 1, 5, 6])) # [1, 2, 5, 5, 6, 9] ``` For $d$ digits and base $b$, the cost is $O(d \cdot (n + b))$. If key width is constant — fixed-width integers, fixed-length strings — this expression reduces to $O(n)$. Variants that start from the most significant digit also exist; they are preferred for sorting text because they provide early discrimination, but they require a recursive structure. #### How "Linear" Is "Linear" All three algorithms surpass the lower bound, but not for free. An honest assessment notes three points. **Assumptions are real constraints.** Counting sort needs a small integer range, bucket sort needs uniform distribution, radix sort needs a fixed-width key. A general-purpose library sort cannot make these assumptions. **Key width depends on $n$.** If $n$ distinct keys are to be distinguished from one another, every key must be at least $\log_2 n$ bits. This is why, in radix sort, the number of digits is $d = \Theta(\log n)$, and the cost actually corresponds to $\Theta(n \log n)$ bit operations. The lower bound is not violated; a different unit of operation has been counted. **Extra space is required.** None of the three is in-place; counting and bucket sort use $O(n + k)$ space. Still, when the conditions hold, the gain is real: sorting millions of records by a fixed-width identifier field is noticeably faster with radix sort than with a comparison-based algorithm. #### Summary - The decision-tree argument shows that comparison-based sorting requires $\Omega(n \log n)$ comparisons in the worst case. - The proof's only assumption is that the algorithm only compares; the bound can be surpassed if the structure of the keys is used. - Counting sort is $O(n + k)$ and stable on a small integer range; traversing in reverse order is the condition for stability. - Bucket sort gives expected $O(n)$ under uniform distribution; the guarantee disappears if the distribution breaks down. - Radix sort runs in $O(d(n + b))$ by using a stable sort at every digit. - Claims of linearity depend on assumptions, and if key width depends on $n$, the lower bound reappears in a different unit. #### Next Step Seven algorithms and a set of distinct criteria have accumulated: worst case, stability, extra space, adaptivity, memory access pattern, and key structure. The next lesson gathers these into a single decision table and answers the question "which algorithm for which data". ### Choosing a Sorting Algorithm Source: https://academia.sh/en/courses/algorithms/choosing-a-sorting-algorithm A decision table based on data characteristics, the use of stability in multi-key sorting, hybrid implementations, and cases where sorting is unnecessary. Seven algorithms and six distinct criteria have accumulated. This lesson gathers them into a single decision framework. The goal is not to memorize a list of sorts, but to see **which property of the data at hand determines the choice**. #### A Combined View of the Criteria | Algorithm | Worst | Average | Extra space | Stable | Adaptive | |---|---|---|---|---|---| | Insertion | $O(n^2)$ | $O(n^2)$ | $O(1)$ | Yes | Yes | | Selection | $O(n^2)$ | $O(n^2)$ | $O(1)$ | No | No | | Bubble | $O(n^2)$ | $O(n^2)$ | $O(1)$ | Yes | Yes | | Merge | $O(n \log n)$ | $O(n \log n)$ | $O(n)$ | Yes | Depends on variant | | Quick | $O(n^2)$ | $O(n \log n)$ | $O(\log n)$ | No | No | | Heap | $O(n \log n)$ | $O(n \log n)$ | $O(1)$ | No | No | | Counting | $O(n + k)$ | $O(n + k)$ | $O(n + k)$ | Yes | No | | Radix | $O(d(n + b))$ | $O(d(n + b))$ | $O(n + b)$ | Yes | No | The table alone does not decide; the problem determines which column matters. #### The Decision Table | Property of the data | Suitable choice | Rationale | |---|---|---| | Few elements (tens) | Insertion | Small constant, simple code | | Nearly sorted | Insertion or run-based merge | Low inversion count | | Stability required | Merge, counting, radix | Stable by definition | | Very tight memory | Heap | $O(1)$ extra space, has a guarantee | | Worst-case guarantee needed | Heap or merge | Does not fall into the quadratic case | | General-purpose, on an array | Hybrid (quick + heap + insertion) | Practical speed and a guarantee | | Linked list | Merge | Sequential access is enough | | Data that does not fit in memory | External merge | Reads as a stream | | Keys are small integers | Counting | $O(n + k)$, no comparison | | Fixed-width key, many records | Radix | Linear per digit | | Many repeated keys | Three-way quicksort | The equal region is never reprocessed | | Only the largest $k$ elements | Heap of size $k$ | $O(n \log k)$, no sorting needed | Most of the rows are not mutually exclusive; if more than one condition holds, the more restrictive one decides. If "stability required" clashes with "tight memory", a stable, in-place algorithm is sought — implementations that give both exist, but their constants are large. #### Hybrid Implementations General-purpose library sorts do not use a single algorithm. Two common designs exist, and both are assembled from this topic's lessons. **Partition-based hybrid.** It starts with quicksort. If recursion depth exceeds the $c \log n$ threshold — meaning the splits keep being unbalanced — it switches to heap sort. Segments below a certain size are left to insertion sort. The result: quicksort's practical speed, heap sort's worst-case guarantee, insertion sort's small constant. **Run-based hybrid.** The **runs** already sorted in the input are found, short runs are extended with insertion sort, and the runs are then merged. It approaches linear on nearly sorted data, is stable, and stays $O(n \log n)$ in the worst case. In exchange, it requires extra space. The shared lesson: real implementations do not claim any single algorithm is best; they use each algorithm in the region where it excels. #### Multi-Key Sorting Stability's most common use is sorting by more than one criterion. There are two routes. **Composite key.** The comparison function evaluates the criteria in order. It finishes in a single pass and does not require stability. **Successive stable sorts.** Sorting is done first by the **secondary** criterion, then by the **primary** one. Because the second sort is stable, the secondary order of elements equal on the primary criterion is preserved. ```python records = [ ("Ankara", 3), ("Izmir", 1), ("Ankara", 1), ("Bursa", 2), ("Izmir", 3), ("Ankara", 2), ] # Secondary criterion (number) first, primary criterion (city) second step1 = sorted(records, key=lambda k: k[1]) step2 = sorted(step1, key=lambda k: k[0]) print(step2) # [('Ankara', 1), ('Ankara', 2), ('Ankara', 3), ('Bursa', 2), ('Izmir', 1), ('Izmir', 3)] # Single pass with a composite key — same result print(sorted(records, key=lambda k: (k[0], k[1])) == step2) # True ``` Both routes give the same result. The successive method is more flexible when the criteria are determined at run time (a table sorted by the column the user picks); the composite key is cheaper because it is a single pass. Radix sort's digit-by-digit operation follows the same principle: every digit is a criterion, and stability preserves the result of the previous criteria. #### Comparison Cost Asymptotic tables count comparison as constant. If the key is complex, this assumption breaks: comparing long strings is proportional to string length, and locale-sensitive sorting rules are far more expensive. Two consequences follow. First, if comparison is expensive, the algorithm that reduces the **number of comparisons** (merge) is preferred; if moving is expensive, the one that reduces moves (selection). Second, an expensive key transformation can be done **once, before** sorting, and cached — not recomputed on every comparison throughout the sort. This is a direct application of the precomputation pattern from the Time and Space Trade-off lesson. #### Cases Where Sorting Is Unnecessary Sorting is an operation that does more than what is needed, and it is often called unnecessarily. | Need | Instead of sorting | Cost | |---|---|---| | The largest or smallest element | A single scan | $O(n)$ | | The kth smallest element | Quickselect | Expected $O(n)$ | | The largest $k$ elements | A heap of size $k$ | $O(n \log k)$ | | Whether a value exists | A hash table | Expected $O(1)$ | | Filtering out duplicates | A hash set | Expected $O(n)$ | | The median value | A selection algorithm | Expected $O(n)$ | If sorting itself is genuinely needed — presenting output in order, preparing for binary search, many-query use — its cost is warranted. Sorting to answer a single question means paying $O(n \log n)$ to do work that is $O(n)$. #### The Point Where Measurement Decides Asymptotic analysis determines the class; choosing within a class requires measurement. If two algorithms are both $O(n \log n)$, the difference lies in the constant, and the constant depends on memory access pattern, key type, data size, and implementation. Three rules apply when measuring: it should be measured **with real data** (random data does not carry the partial ordering of real data), it should be measured **with the input size varied** (a single size does not reveal the class), and how the measured durations scale with the input should be examined — the scale-growth table from the Reading Complexity Classes lesson is for exactly this job. #### Summary - The choice comes from the data's properties, not from the algorithm itself: size, partial ordering, the proportion of repeated keys, key structure, memory constraint, and the stability requirement. - General-purpose implementations are hybrids; they use each algorithm in the region where it excels. - Multi-key sorting is done with successive stable sorts or with a composite key. - If comparison is expensive, the algorithm that reduces comparisons is chosen; if moving is expensive, the one that reduces moves. - Sorting is unnecessary for minimum, kth, first-$k$, or existence questions; linear or expected-constant-cost solutions exist. - The decision within a class is given by measurement; measurement is done with real data and at more than one input size. #### Next Step Searching and sorting have worked on one-dimensional data: elements had only an ordering relation between them. The next topic moves to data where elements have **connections**. The Data Structures course defined graphs and built breadth-first and depth-first search; now the problems of shortest path, minimum spanning tree, and maximum flow in weighted graphs will be covered. ## Graph Algorithms Shortest-path algorithms, heuristic search, minimum spanning tree, and network flow. ### Dijkstra's Algorithm Source: https://academia.sh/en/courses/algorithms/dijkstras-algorithm Single-source shortest path on a weighted graph, the relaxation operation, the justification for the greedy choice, a priority-queue implementation, and the non-negative weight restriction. The Data Structures course defined graphs and established breadth-first and depth-first search. Breadth-first search found the shortest path in terms of **edge count**: every edge was counted as equally costly. In real problems, edges carry different costs — distance, time, fare. This topic builds algorithms that work on weighted graphs, and its first question is the shortest path. #### Problem and Notation **Single-source shortest path problem:** Given a weighted graph and a source vertex, find the paths of lowest total weight from the source to every other vertex. The same graph is used throughout this topic: vertices `A`–`F`, edges directed and weighted. ```python graph: dict[str, list[tuple[str, int]]] = { "A": [("B", 4), ("C", 2)], "B": [("C", 5), ("D", 10)], "C": [("E", 3)], "D": [("F", 11)], "E": [("D", 4)], "F": [], } ``` The adjacency list representation suits sparse graphs, and traversing all edges is $O(V + E)$. In dense graphs the adjacency matrix is preferred; the cost impact of this choice was covered in the Data Structures course. #### Relaxation The common building block of these algorithms is **relaxation**: lowering a known estimate using a better path that has been found. For each vertex, the best known distance from the source is kept as `u[v]`; initially $0$ for the source and infinity for the rest. For an edge `(v, w)`: $$ u[w] > u[v] + \text{weight}(v, w) \implies u[w] \leftarrow u[v] + \text{weight}(v, w) $$ Relaxation never produces an incorrect value: `u[w]` is always the length of a **path that actually exists**. Algorithms differ in the guarantee they give about when these values become final. #### The Greedy Choice Dijkstra's algorithm rests on this idea: **among vertices not yet settled, the one with the smallest estimate is now settled.** The justification rests on weights being non-negative. Any other path from the source to `v` must pass through an unsettled vertex; since that vertex's estimate is not smaller than `u[v]`, and the remaining edges cannot reduce the cost, the alternative path cannot be shorter. This reasoning gives the algorithm's invariant: **the distances of settled vertices are the true shortest-path lengths.** #### Implementation ```python import heapq def dijkstra(graph: dict[str, list[tuple[str, int]]], source: str) -> tuple[dict[str, float], dict[str, str | None]]: """Returns (distances, previous vertices). Weights must not be negative.""" distance: dict[str, float] = {vertex: float("inf") for vertex in graph} previous: dict[str, str | None] = {vertex: None for vertex in graph} distance[source] = 0 queue: list[tuple[float, str]] = [(0, source)] settled: set[str] = set() while queue: dist, v = heapq.heappop(queue) if v in settled: # stale entry: skip continue settled.add(v) for neighbor, weight in graph[v]: if dist + weight < distance[neighbor]: distance[neighbor] = dist + weight previous[neighbor] = v heapq.heappush(queue, (distance[neighbor], neighbor)) return distance, previous distance, previous = dijkstra(graph, "A") print(distance) # {'A': 0, 'B': 4, 'C': 2, 'D': 9, 'E': 5, 'F': 20} ``` The direct route from `A` to `D` via `A→B→D` has length 14; the algorithm finds the `A→C→E→D` path with length 9. The greedy choice does not prevent a start that looks longer from summing to less — because the choice looks at accumulated distances, not at individual edges. #### Reconstructing the Path Distance alone is not enough; which path was taken is also needed. The `previous` dictionary carries this information: each vertex points to the vertex it was reached from on the shortest path. ```python def build_path(previous: dict[str, str | None], target: str) -> list[str]: path: list[str] = [] vertex: str | None = target while vertex is not None: path.append(vertex) vertex = previous[vertex] return path[::-1] print(build_path(previous, "F")) # ['A', 'C', 'E', 'D', 'F'] print(build_path(previous, "B")) # ['A', 'B'] ``` These pointers form a **shortest path tree**: a tree rooted at the source that jointly encodes the shortest paths to every vertex. #### Cost Every vertex is settled at most once; every edge produces at most one relaxation and one queue insertion. With a binary heap: $$ O\big((V + E)\log V\big) $$ The queue can hold multiple entries for the same vertex — the implementation here skips stale entries as they are popped. This **lazy deletion** gives the same asymptotic bound without requiring a priority queue with a decrease-key operation, and it shortens the code noticeably. In dense graphs ($E \approx V^2$), a variant that scans an array instead of using a queue is $O(V^2)$ and can be faster. A theoretical variant using a Fibonacci heap gives $O(E + V \log V)$; its constants are large, so it is rarely seen in practice. #### Common Variants The basic structure adapts to different questions with small changes. **Early exit for a single target.** If only the distance to a specific vertex is needed, the search can stop the moment that vertex is popped from the queue; its value is settled at that point. The remaining vertices are never processed. **Multi-source search.** For questions like "distance to the nearest warehouse," all sources are placed in the queue with zero distance at the start. This is equivalent to a graph where a single artificial source draws a zero-weight edge to every warehouse; it is the weighted counterpart of the multi-source breadth-first search from the Data Structures course. **Unreachable vertices.** The distance of a vertex unreachable from the source stays infinite. Code that uses the result must test for this value; treating infinity as an ordinary numeric distance leads to silent errors. **Weights restricted to 0 and 1.** In this case a double-ended queue suffices instead of a priority queue: a zero-weight edge is added to the front, a one-weight edge to the back. The cost drops to $O(V + E)$ — the logarithmic factor is the price of weight variety. #### The Non-Negative Weight Restriction The algorithm's correctness rested on the assumption that "a settled vertex's value can never drop again." A negative-weight edge breaks this assumption. ```python with_negative_weight = { "A": [("B", 1), ("C", 2)], "B": [("D", 1)], "C": [("B", -2)], "D": [], } print(dijkstra(with_negative_weight, "A")[0]) # {'A': 0, 'B': 0, 'C': 2, 'D': 2} — D wrong: the true distance is 1 ``` Vertex `B` is settled via the direct edge of weight 1, and `D` is relaxed to 2 through it. Then `C` is processed, and it turns out the `A→C→B` path is $2 + (-2) = 0$; `B`'s value is corrected, but since `B` is already counted as settled, its outgoing edges are never relaxed again. `D` stays at its old value. The algorithm raises no error; **it silently produces the wrong result.** This is one of the examples showing why documenting preconditions is not a formality. An algorithm that works with negative weights is the subject of the next lesson. #### Summary - The single-source shortest path problem asks for the lowest total-cost paths from the source to every vertex in a weighted graph. - Relaxation lowers a vertex's estimated distance using a better path that has been found, and every estimate corresponds to a real path. - Dijkstra's algorithm picks the smallest estimate among unsettled vertices; its correctness rests on weights being non-negative. - The priority-queue implementation is $O((V + E)\log V)$; lazy deletion avoids needing a decrease-key operation. - Previous-vertex pointers encode the shortest path tree and allow the path to be reconstructed. - Under negative weight, the algorithm produces the wrong result without raising an error. #### Next Step Negative weights arise in real problems: gain in currency conversion cycles, recovery in a production plan. The next lesson builds the Bellman–Ford algorithm, which abandons the greedy choice and relaxes every edge repeatedly, and shows why negative cycles make the problem undefined. ### Bellman–Ford Algorithm Source: https://academia.sh/en/courses/algorithms/bellman-ford-algorithm Relaxation by iterating over all edges, induction on edge count, negative cycle detection, and the linear solution on a directed acyclic graph. Dijkstra's algorithm never returned to a vertex once it was settled; this was a gain that rested on weights being non-negative. If a negative weight exists, a vertex's value can drop later, and a single pass is not enough. Bellman–Ford abandons this assumption: it settles no vertex, and instead relaxes **all edges, repeatedly**. #### The Algorithm All distances except the source start at infinity. Then $V-1$ passes are made over all edges; each pass relaxes every edge once. ```python def bellman_ford(graph: dict[str, list[tuple[str, int]]], source: str) -> tuple[dict[str, float], bool]: """Returns (distances, whether a negative cycle exists).""" distance: dict[str, float] = {vertex: float("inf") for vertex in graph} distance[source] = 0 edges = [(v, w, weight) for v in graph for w, weight in graph[v]] for _ in range(len(graph) - 1): changed = False for v, w, weight in edges: if distance[v] + weight < distance[w]: distance[w] = distance[v] + weight changed = True if not changed: # early exit: nothing improved break for v, w, weight in edges: # one more pass, if it still improves if distance[v] + weight < distance[w]: return distance, True return distance, False with_negative_weight = { "A": [("B", 1), ("C", 2)], "B": [("D", 1)], "C": [("B", -2)], "D": [], } print(bellman_ford(with_negative_weight, "A")) # ({'A': 0, 'B': 0, 'C': 2, 'D': 1}, False) ``` The `D` distance that the previous lesson's Dijkstra computed incorrectly comes out correct here: 1. The difference is that `B`'s outgoing edges are relaxed again after its value drops. The same algorithm is also correct on graphs without negative weight; Dijkstra's edge is not correctness but speed. #### Why $V-1$ Passes The justification is induction on the edge count of a path. **Claim:** After the $k$-th pass, every shortest path using at most $k$ edges has been computed correctly. The base case is $k = 0$: the source's distance is zero. For the step, let the last edge of a shortest path with at most $k+1$ edges be $(v, w)$. The portion of the path up to `v` uses at most $k$ edges and, by the induction hypothesis, is correct after the $k$-th pass; when this edge is relaxed on the $(k+1)$-th pass, `w` also gets its correct value. If there is no negative cycle, no shortest path visits a vertex twice, so it contains at most $V-1$ edges. This is why $V-1$ passes suffice. The early exit noticeably reduces the number of passes in practice: if no value improved in one pass, later passes will not improve anything either. #### Negative Cycle If an edge still relaxes after $V-1$ passes, a **negative cycle** reachable from the source exists. ```python cyclic = { "A": [("B", 1)], "B": [("C", -3)], "C": [("B", 1)], # B → C → B cycle: -3 + 1 = -2 } print(bellman_ford(cyclic, "A")[1]) # True ``` In such a cycle the problem is **undefined**: the total cost drops every time the cycle is traversed, so there is no such thing as "the shortest path." Detection is done not to salvage the computed values, but to report the problem itself. The ability to detect negative cycles is not a byproduct — it is one of the algorithm's main uses. The classic application is detecting arbitrage: if the multiplicative gain of exchange rates is converted to additive cost by a $-\log$ transform, a profitable cycle becomes a negative cycle, and the algorithm finds it. #### Marking the Affected Vertices Knowing that a negative cycle exists is often not enough; **which vertices** are affected by it is also asked. The distance of every vertex reachable from the cycle can be made arbitrarily small, that is, negative infinity; the values of the remaining vertices are valid. The distinction is made by running $V-1$ more passes and marking the targets of edges that still relax as negative infinity. ```python def bellman_ford_marked(graph: dict[str, list[tuple[str, int]]], source: str) -> dict[str, float]: distance: dict[str, float] = {vertex: float("inf") for vertex in graph} distance[source] = 0 edges = [(v, w, weight) for v in graph for w, weight in graph[v]] for _ in range(len(graph) - 1): for v, w, weight in edges: if distance[v] + weight < distance[w]: distance[w] = distance[v] + weight for _ in range(len(graph) - 1): # propagate negative infinity for v, w, weight in edges: if distance[v] != float("inf") and ( distance[v] + weight < distance[w] or distance[v] == float("-inf") ): distance[w] = float("-inf") return distance wide_cycle = { "A": [("B", 1)], "B": [("C", -3)], "C": [("B", 1), ("D", 2)], "D": [], "E": [("A", 1)], # unreachable from the source } print(bellman_ford_marked(wide_cycle, "A")) # {'A': 0, 'B': -inf, 'C': -inf, 'D': -inf, 'E': inf} ``` Three separate cases appear in the same dictionary: a valid distance (`A`), vertices affected by the negative cycle (`B`, `C`, `D`), and an unreachable vertex (`E`). Code that uses a result must distinguish all three cases. #### Cost Every pass processes all edges, and at most $V-1$ passes are made: $$ O(V \cdot E) $$ This is noticeably more expensive than Dijkstra's $O((V+E)\log V)$. The space cost is $O(V)$. | Criterion | Dijkstra | Bellman–Ford | |---|---|---| | Negative weight | Not accepted | Accepted | | Negative cycle | Not detected | Detected | | Cost | $O((V+E)\log V)$ | $O(V \cdot E)$ | | Approach | Greedy | Iterative relaxation | The choice is clear: Dijkstra when weights cannot be negative, Bellman–Ford when they can. If distances between all pairs of vertices are needed, algorithms designed for all pairs at once are used instead of running each vertex separately; these are the subject of the Advanced Algorithms course. #### A Cheaper Path in Acyclic Graphs If the graph is **directed and acyclic (a DAG)**, a single pass suffices once the relaxation order is chosen correctly, since there is no cycle. The correct order is the topological order from the Data Structures course: when a vertex is processed, every edge arriving at it has already been relaxed. ```python def dag_shortest_path(graph: dict[str, list[tuple[str, int]]], order: list[str], source: str) -> dict[str, float]: """order: a topological order. Cost O(V + E).""" distance: dict[str, float] = {vertex: float("inf") for vertex in graph} distance[source] = 0 for v in order: if distance[v] == float("inf"): continue for w, weight in graph[v]: if distance[v] + weight < distance[w]: distance[w] = distance[v] + weight return distance graph = { "A": [("B", 4), ("C", 2)], "B": [("C", 5), ("D", 10)], "C": [("E", 3)], "D": [("F", 11)], "E": [("D", 4)], "F": [], } print(dag_shortest_path(graph, ["A", "B", "C", "E", "D", "F"], "A")) # {'A': 0, 'B': 4, 'C': 2, 'D': 9, 'E': 5, 'F': 20} ``` The result is the same one Dijkstra's algorithm finds on the same graph; the cost, however, drops to $O(V + E)$. Moreover, this method also accepts **negative weights**, because it makes no greedy choice. The same structure is also used to find the **longest** path: the comparison direction is reversed. In general graphs the longest path problem is hard; acyclicity makes it linear. The critical path calculation in project planning is of this kind. #### Summary - Bellman–Ford settles no vertex; it relaxes all edges over $V-1$ passes. - After the $k$-th pass, every shortest path with at most $k$ edges is correct; without a negative cycle, a shortest path contains at most $V-1$ edges. - An edge that still relaxes on the $V$-th pass means a negative cycle reachable from the source, and the problem is undefined. - The cost is $O(V \cdot E)$; the early exit reduces the number of passes in practice. - Dijkstra is chosen when weights cannot be negative, Bellman–Ford when they can. - In acyclic graphs, a single pass in topological order suffices, and the cost is $O(V + E)$. #### Next Step Both algorithms so far searched without a target: distance was computed from the source to **every** vertex. This is wasteful if a specific target is the goal. The next lesson narrows the search with an estimating function that knows the target's direction — the A* algorithm — and examines the condition under which the estimate does not break correctness. ### A* Search Source: https://academia.sh/en/courses/algorithms/a-star-search Target-directed search with a heuristic function, admissibility and consistency conditions, the relation to Dijkstra, and the gain in expanded vertex count. The previous two algorithms computed distance from the source to **every** vertex. This is wasteful if a specific target is the goal: vertices in the opposite direction from the target are processed with the same care. A* reduces this waste by folding an estimate of where the target lies into the search. #### The Evaluation Function Two quantities are kept for each vertex: - $g(v)$ — the best known cost from the source to `v` (the distance in Dijkstra's algorithm). - $h(v)$ — the **estimated** remaining cost from `v` to the target; it comes from knowledge of the problem. The search proceeds by their sum: $$ f(v) = g(v) + h(v) $$ $f(v)$ is the estimated total cost of a solution passing through `v`. The priority queue orders not by distance but by this value; everything else is the same as Dijkstra's algorithm. ```python import heapq def a_star(graph: dict[str, list[tuple[str, int]]], start: str, target: str, h: dict[str, int]) -> float | None: g: dict[str, float] = {start: 0} open_set: list[tuple[float, float, str]] = [(h[start], 0, start)] closed: set[str] = set() while open_set: _, cost, vertex = heapq.heappop(open_set) if vertex in closed: continue closed.add(vertex) if vertex == target: return cost for neighbor, weight in graph[vertex]: new_cost = cost + weight if new_cost < g.get(neighbor, float("inf")): g[neighbor] = new_cost heapq.heappush(open_set, (new_cost + h[neighbor], new_cost, neighbor)) return None ``` If $h(v) = 0$ for every vertex, $f = g$ and the algorithm becomes exactly Dijkstra's algorithm. A* is, in this sense, a generalization of Dijkstra: the heuristic is the extra information added to the search. #### Admissibility The heuristic cannot be arbitrary. Being **admissible** means it never **exceeds** the true remaining cost at any vertex: $$ h(v) \leq h^*(v) $$ Here $h^*(v)$ is the true remaining cost. With an admissible heuristic, A* guarantees that the first solution it finds is optimal. Justification: when the target reaches the front of the queue, $f(\text{target}) = g(\text{target})$. If a better solution existed, a vertex on that solution's path would be in the queue, and — since estimates never overshoot — its $f$ value would be smaller than the true total cost, so it would be popped before the target. If the condition is violated, optimality is lost. ```python graph = { "A": [("B", 1), ("C", 5)], "B": [("H", 10)], "C": [("H", 1)], "H": [], } overestimating = {"A": 0, "B": 1, "C": 10, "H": 0} # C's estimate is far above the true value (1) admissible = {"A": 6, "B": 10, "C": 1, "H": 0} print(a_star(graph, "A", "H", overestimating)) # 11 — not optimal print(a_star(graph, "A", "H", admissible)) # 6 print(a_star(graph, "A", "H", {v: 0 for v in graph})) # 6 — Dijkstra ``` The overestimate causes the true shortest path through `C` (`A→C→H`, 6) to be pruned away; the algorithm returns the `A→B→H` path (11) instead. #### Consistency A stronger condition is **consistency**: for every edge `(v, w)`, $$ h(v) \leq \text{weight}(v, w) + h(w) $$ This is the heuristic's counterpart of the triangle inequality. A consistent heuristic is admissible and additionally guarantees the following: when a vertex is closed, its $g$ value is final, so no vertex is ever expanded twice. With a heuristic that is admissible but not consistent, the $g$ value of a closed vertex may not be final. Optimality is preserved only if a closed vertex is **reopened** when it is reached by a cheaper path; the implementation above skips closed vertices unconditionally, so with such a heuristic it can return a path that is not optimal. Most heuristics used in practice — straight-line distance on a plane, Manhattan distance on a grid — are consistent, so the situation does not arise. #### The Measured Gain The gain shows up in the **number of expanded vertices**. In the grid below, every step costs one unit; neighbors lie in four directions. ```python def grid_search(grid: list[str], start: tuple[int, int], target: tuple[int, int], heuristic) -> tuple[int, int]: """(path cost, number of expanded vertices)""" g = {start: 0} open_set = [(heuristic(start, target), 0, start)] closed: set[tuple[int, int]] = set() count = 0 while open_set: _, cost, vertex = heapq.heappop(open_set) if vertex in closed: continue closed.add(vertex) count += 1 if vertex == target: return cost, count row, col = vertex for dr, dc in ((-1, 0), (0, -1), (0, 1), (1, 0)): r, c = row + dr, col + dc if 0 <= r < len(grid) and 0 <= c < len(grid[0]) and grid[r][c] != "#": new_cost = cost + 1 if new_cost < g.get((r, c), float("inf")): g[(r, c)] = new_cost heapq.heappush(open_set, (new_cost + heuristic((r, c), target), new_cost, (r, c))) return -1, count zero = lambda a, b: 0 manhattan = lambda a, b: abs(a[0] - b[0]) + abs(a[1] - b[1]) open_grid = ["." * 15 for _ in range(15)] walled = ["".join("#" if (2 <= r <= 12 and c == 7) else "." for c in range(15)) for r in range(15)] print(grid_search(open_grid, (7, 1), (7, 13), zero)) # (12, 147) print(grid_search(open_grid, (7, 1), (7, 13), manhattan)) # (12, 13) print(grid_search(walled, (7, 1), (7, 13), zero)) # (24, 212) print(grid_search(walled, (7, 1), (7, 13), manhattan)) # (24, 169) ``` On the open grid, A* follows the strip leading to the target and expands 13 vertices instead of 147. The path cost is identical — the gain is not in correctness, but in work spent. On the walled grid, the gain erodes: Manhattan distance does not see the wall, so the estimate stays far below the truth and the heuristic does not narrow the search direction enough. **A heuristic's quality is measured by how close it comes to the truth**; every point between $h = 0$ and $h = h^*$ lies somewhere between Dijkstra and walking straight to the target. #### Trade-offs **Memory.** A* stores every vertex in the open set; in large search spaces, memory is as limiting as time. Variants that iterate by increasing depth ($O(b\,d)$ memory) solve this problem at a cost. **Deliberate overestimation.** Scaling the heuristic by a factor narrows the search but breaks optimality; it is used knowing the solution found may be worse by that factor. This is a reasonable trade-off when a fast answer is worth more than an optimal one. **The heuristic's own cost.** $h$ is computed for every vertex; an expensive heuristic can take away more than the expansions it saves. These trade-offs are the artificial-intelligence side of search, and together with game trees they are the subject of the AI Engineering curriculum; they are not treated here. #### Summary - A* expands vertices by their $f(v) = g(v) + h(v)$ value; with $h = 0$ it reduces to Dijkstra's algorithm. - An admissible heuristic never exceeds the true remaining cost and guarantees the solution found is optimal. - A consistent heuristic satisfies the triangle inequality; no vertex is ever expanded twice. - The gain shows up in the number of expanded vertices and is proportional to how close the heuristic is to the truth. - Obstacles push the estimate further from the truth and reduce the gain. - Memory use, deliberate overestimation, and the heuristic's own computational cost are the main trade-offs. #### Next Step The question asked so far has been "what is the cheapest path between two vertices." The next lesson changes the question: what is the cheapest set of edges connecting all vertices to each other? The minimum spanning tree problem will establish the correctness of a greedy choice on different grounds — the cut property. ### Minimum Spanning Tree Source: https://academia.sh/en/courses/algorithms/minimum-spanning-tree The cut property, Prim's and Kruskal's algorithms, the union-find structure, a comparison of the two approaches, and a clustering application. The questions so far concerned the path between two vertices. This lesson changes the question: **what is the cheapest set of edges that connects all vertices to each other?** The question is the basic form of network design: every point must be connected, and the total cable, pipe, or line cost must be minimized. #### The Problem In a weighted, undirected, connected graph, a **spanning tree** is a subgraph that includes every vertex and contains no cycle. Such a subgraph has exactly $V-1$ edges. A **minimum spanning tree (MST)** is the spanning tree whose sum of edge weights is smallest. If the weights are all distinct, the MST is unique; if equal weights exist, more than one MST may exist, and all of them have the same total weight. The graph used throughout this lesson is undirected: ```python edges: list[tuple[int, str, str]] = [ (4, "A", "B"), (2, "A", "C"), (5, "B", "C"), (10, "B", "D"), (3, "C", "E"), (4, "E", "D"), (11, "D", "F"), ] vertices = ["A", "B", "C", "D", "E", "F"] ``` #### The Cut Property Both algorithms are greedy, and their correctness rests on a single observation. A **cut** splits the vertices into two non-empty parts. An edge **crosses** the cut if its endpoints lie in different parts. **Cut property:** The lightest edge crossing any cut is present in some minimum spanning tree. The justification is an **exchange argument**. Let $e$ be the lightest crossing edge, and consider an MST that does not contain it. Adding $e$ to this tree creates a cycle; the cycle must cross the cut at least once more. Let that crossing edge be $f$. Removing $f$ and adding $e$ yields another spanning tree whose weight has not increased, because $e \leq f$. Hence an MST containing $e$ also exists. This property justifies every greedy strategy of the form "take the cheapest edge that is currently safe." The two algorithms differ only in **which cut** they look at. #### Prim's Algorithm The tree starts from a single vertex and grows on every step. The cut examined is the one between the vertices already in the tree and those outside it; the edge chosen is the lightest one crossing this cut. ```python import heapq from collections import defaultdict def build_adjacency(edges: list[tuple[int, str, str]]) -> dict[str, list[tuple[int, str]]]: adjacency: dict[str, list[tuple[int, str]]] = defaultdict(list) for weight, v, w in edges: adjacency[v].append((weight, w)) adjacency[w].append((weight, v)) return adjacency def prim(edges: list[tuple[int, str, str]], start: str) -> tuple[list[tuple[int, str, str]], int]: adjacency = build_adjacency(edges) in_tree = {start} queue = [(weight, start, w) for weight, w in adjacency[start]] heapq.heapify(queue) tree: list[tuple[int, str, str]] = [] while queue: weight, v, w = heapq.heappop(queue) if w in in_tree: # both ends already in the tree: cycle continue in_tree.add(w) tree.append((weight, v, w)) for edge_weight, neighbor in adjacency[w]: if neighbor not in in_tree: heapq.heappush(queue, (edge_weight, w, neighbor)) return tree, sum(weight for weight, _, _ in tree) print(prim(edges, "A")) # ([(2, 'A', 'C'), (3, 'C', 'E'), (4, 'A', 'B'), (4, 'E', 'D'), (11, 'D', 'F')], 24) ``` The structure closely resembles Dijkstra's algorithm; the only difference is that the priority is **distance to the tree**, not **distance from the source**. The cost is also the same: $O(E \log V)$ with a binary heap. #### Kruskal's Algorithm Kruskal does not grow a tree; it sorts the edges by weight and adds them in order. An edge is skipped when its two endpoints are **already in the same component**, since adding it would create a cycle. This check uses a **union-find** structure: a structure that reports, at nearly constant cost, which component each vertex belongs to. ```python class UnionFind: def __init__(self, vertices: list[str]) -> None: self.parent = {v: v for v in vertices} self.rank = {v: 0 for v in vertices} def find(self, v: str) -> str: while self.parent[v] != v: self.parent[v] = self.parent[self.parent[v]] # path compression v = self.parent[v] return v def union(self, a: str, b: str) -> bool: ra, rb = self.find(a), self.find(b) if ra == rb: return False # already the same component if self.rank[ra] < self.rank[rb]: # union by rank ra, rb = rb, ra self.parent[rb] = ra if self.rank[ra] == self.rank[rb]: self.rank[ra] += 1 return True def kruskal(edges: list[tuple[int, str, str]], vertices: list[str]) -> tuple[list[tuple[int, str, str]], int]: components = UnionFind(vertices) tree: list[tuple[int, str, str]] = [] for weight, v, w in sorted(edges): if components.union(v, w): tree.append((weight, v, w)) if len(tree) == len(vertices) - 1: # tree complete break return tree, sum(weight for weight, _, _ in tree) print(kruskal(edges, vertices)) # ([(2, 'A', 'C'), (3, 'C', 'E'), (4, 'A', 'B'), (4, 'E', 'D'), (11, 'D', 'F')], 24) ``` The two algorithms find the same tree on this graph. In general only the **total weight** is guaranteed to match; if equal-weight edges exist, they can produce different trees of equal total weight. The cut here is "the component of one endpoint of the edge being tried" versus the remaining vertices; the edge is the lightest one crossing that cut, because lighter ones have already been tried. When **path compression** and **union by rank** are used together, the amortized cost of union-find operations is nearly constant — its growth is bounded by the inverse Ackermann function and is smaller than four in practice. #### Comparison | Criterion | Prim | Kruskal | |---|---|---| | Approach | Grow the tree | Add edges in order | | Helper structure | Priority queue | Union-find | | Cost | $O(E \log V)$ | $O(E \log E)$ | | Dense graph | Suits it (array variant gives $O(V^2)$) | Sorting dominates | | Disconnected graph | Finds only one component | Produces a spanning **forest** | Sorting dominates Kruskal's cost; if the edges are already sorted, the cost drops to nearly linear. Prim gains the edge as the edge count approaches the square of the vertex count. One distinction is decisive in practice: if the graph is not connected, Kruskal produces one tree per component, and the result is a spanning forest; Prim covers only the component of the starting vertex. #### A Clustering Application Kruskal's intermediate steps are meaningful on their own: when the algorithm has added $V-k$ edges, $k$ components remain, and these components are the $k$ clusters that are **farthest apart from each other**. This is the single-linkage clustering method: distances between points are treated as edge weights, an MST is built, and the heaviest $k-1$ edges are discarded. The result is the split that maximizes the minimum distance between clusters. The same structure is also used in network design and in approximate solutions: in the metric case of the traveling salesman problem, the MST gives a lower bound on the length of the optimal tour and helps produce a tour that does not exceed twice that length. #### Summary - A spanning tree connects all vertices acyclically and contains $V-1$ edges; a minimum spanning tree is the lightest of these. - The cut property states that the lightest edge crossing any cut is present in some MST, and it justifies the greedy choices. - Prim grows a tree and uses a priority queue; its cost is $O(E \log V)$. - Kruskal sorts edges and checks cycles with union-find; its cost is $O(E \log E)$. - Path compression and union by rank make union-find operations amortized nearly constant. - Kruskal's intermediate states produce clustering; an MST also provides a lower bound in approximate solutions. #### Next Step Until now, edges carried a cost. The next lesson gives edges a different meaning: **capacity**. How much can be pushed from a source to a target through a network is now an optimization problem defined on a graph, and its answer arrives with an unexpected equality — the equality between maximum flow and minimum cut. ### Network Flow Source: https://academia.sh/en/courses/algorithms/network-flow The definition of a flow network, the residual network and augmenting paths, the Ford–Fulkerson method with the Edmonds–Karp variant, the max-flow min-cut theorem, and a matching application. Edges have carried cost so far: length, time, fare. This lesson gives edges a different meaning — **capacity**. The question is no longer "which is the cheapest path" but "how much can be pushed from a source to a target." The problem gathers a wide family — from pipelines to communication networks to task assignment — under a single roof. #### Flow Network A **flow network** is a directed graph in which every edge carries a non-negative capacity. There are two special vertices: the **source** and the **sink**. A flow assigns a value to every edge and satisfies two constraints: **Capacity constraint.** The flow on any edge cannot exceed its capacity. **Conservation constraint.** At every vertex other than the source and the sink, flow in equals flow out. **The value of a flow** is the net flow leaving the source. The goal is to maximize this value. ```python capacity: dict[str, dict[str, int]] = { "S": {"A": 10, "C": 10}, "A": {"B": 4, "C": 2, "D": 8}, "B": {"T": 10}, "C": {"D": 9}, "D": {"B": 6, "T": 10}, "T": {}, } ``` The total capacity leaving the source is 20, but this is only an upper bound — the network's internal structure may impose a lower ceiling. #### Residual Network and Augmenting Path A greedy approach — "find an empty path, fill it, repeat" — gives the wrong result: a choice made early can block a better distribution found later, and it cannot be undone. The solution is the concept of a **residual network**. In the residual network, two values are kept for every edge: - The forward remaining capacity: capacity minus the current flow. - A backward capacity equal to the current flow. The backward edge is the ability to "cancel the flow sent along this edge." No choice is ever permanently wrong this way — the algorithm can correct its own earlier decision later. Any path from the source to the sink in the residual network is called an **augmenting path**. The amount that can be sent along the path is its smallest remaining capacity (the bottleneck). **Ford–Fulkerson method:** Find an augmenting path while one remains, and increase the flow along it. #### The Edmonds–Karp Variant The method does not say **how** the augmenting path should be chosen. If the path is chosen by breadth-first search every time — that is, as the path with the fewest edges — the resulting variant costs $O(V \cdot E^2)$ and terminates regardless of the choice. ```python from collections import deque, defaultdict def residual_network(capacity: dict[str, dict[str, int]]) -> dict[str, dict[str, int]]: residual: dict[str, dict[str, int]] = defaultdict(dict) for v in capacity: for w, c in capacity[v].items(): residual[v][w] = c residual[w].setdefault(v, 0) # backward edge: starts at zero return residual def edmonds_karp(capacity: dict[str, dict[str, int]], source: str, sink: str) -> tuple[int, set[str]]: """(maximum flow, vertices reachable from the source in the residual network)""" residual = residual_network(capacity) total = 0 while True: previous: dict[str, str | None] = {source: None} queue = deque([source]) while queue and sink not in previous: v = queue.popleft() for w, c in residual[v].items(): if c > 0 and w not in previous: previous[w] = v queue.append(w) if sink not in previous: # no augmenting path left return total, set(previous) v, bottleneck = sink, float("inf") while previous[v] is not None: # find the bottleneck bottleneck = min(bottleneck, residual[previous[v]][v]) v = previous[v] v = sink while previous[v] is not None: # send the flow, grow the backward edge residual[previous[v]][v] -= bottleneck residual[v][previous[v]] += bottleneck v = previous[v] total += bottleneck flow, reachable = edmonds_karp(capacity, "S", "T") print(flow, sorted(reachable)) # 19 ['C', 'S'] ``` Against the 20 units of capacity leaving the source, the maximum flow is 19. What sets the limit is stored in the second returned value. #### Maximum Flow – Minimum Cut A **cut** splits the vertices into two parts, one containing the source, the other the sink. The cut's capacity is the sum of the capacities of the edges going from the source's side to the sink's side. Every flow's value is less than or equal to every cut's capacity — a flow must cross the cut. The **theorem** says something stronger: $$ \text{maximum flow} = \text{minimum cut capacity} $$ The justification follows from the algorithm. When the algorithm stops, there is no path from the source to the sink in the residual network; the vertices reachable from the source define a cut. Every forward edge crossing this cut is full (otherwise reachability would continue), and every backward edge is empty. So the value of the flow is exactly equal to this cut's capacity. ```python cut = [(v, w) for v in capacity for w in capacity[v] if v in reachable and w not in reachable] print(cut) # [('S', 'A'), ('C', 'D')] print(sum(capacity[v][w] for v, w in cut)) # 19 ``` The result is not just a number but a **diagnosis**: the network's bottleneck is the `S→A` and `C→D` edges. If capacity is to be increased, expanding any other edge will not increase the flow. A byproduct of the theorem is the **integrality property**: if the capacities are integers, some maximum flow is also integer-valued. This is decisive in problems where the flow can be interpreted as the assignment of discrete objects. #### Reduction: Bipartite Matching The power of network flow lies in other problems being **reducible** to it. The maximum matching problem on a bipartite graph is this: match every left vertex to a right vertex connected to it by an edge, with no vertex used twice. The reduction is simple: 1-capacity edges from an artificial source to the left vertices, 1 capacity on the existing edges, 1-capacity edges from the right vertices to an artificial sink. ```python def maximum_matching(left: list[str], right: list[str], links: dict[str, list[str]]) -> int: network: dict[str, dict[str, int]] = defaultdict(dict) for v in left: network["S"][v] = 1 for v, targets in links.items(): for w in targets: network[v][w] = 1 for w in right: network[w]["T"] = 1 network["T"] = {} return edmonds_karp(network, "S", "T")[0] print(maximum_matching(["a1", "a2", "a3"], ["i1", "i2", "i3"], {"a1": ["i1", "i2"], "a2": ["i1"], "a3": ["i2", "i3"]})) # 3 print(maximum_matching(["a1", "a2", "a3"], ["i1", "i2", "i3"], {"a1": ["i1"], "a2": ["i1"], "a3": ["i1"]})) # 1 ``` In the first example, all three candidates are placed in different jobs; in the second, all three want the same job, so only one can be placed. The integrality property is essential here: a half matching would be meaningless. The same method also converts problems such as task assignment, the count of disjoint paths, and project selection into flow. Reduction is one of the central techniques of algorithm design, and it will also be used in the **Theory of Computation** course to define complexity classes. #### Termination and Sensitivity to Choice The Ford–Fulkerson method can cause trouble when the augmenting path is chosen arbitrarily: if paths that augment by a very small amount are chosen at every step, the number of steps can equal the flow's **value** even with integer capacities. If the capacities are not integers, the method may never terminate at all. Choosing by breadth-first search (Edmonds–Karp) removes this problem: the length of augmenting paths never decreases, and the total number of steps is bounded by $O(V \cdot E)$. This is a concrete example of the distinction between a "method" and an "algorithm" — what turns a method into an algorithm is pinning down the choice it leaves open. #### Summary - A flow network consists of edges with capacity; a flow satisfies the capacity and conservation constraints. - Backward edges in the residual network allow earlier decisions to be undone and fix the greedy approach's error. - Ford–Fulkerson grows the flow as long as an augmenting path remains; Edmonds–Karp chooses the path by breadth-first search and gives the $O(V E^2)$ bound. - Maximum flow equals minimum cut capacity; the set reachable in the residual network gives that cut. - If the capacities are integers, some maximum flow is integer-valued. - Problems such as bipartite matching are solved by reducing them to a flow network. #### Next Step Graph algorithms worked on data with connections between elements. The next topic moves to a different structure: **sequences of symbols in order**. Searching for a pattern in text looks, at first glance, like a linear scan, but it speeds up noticeably once the pattern's own structure is used. The topic will begin by measuring the cost of brute-force search. ## Text Algorithms Pattern-matching methods, preprocessing structures, and lossless compression. ### Brute-Force Pattern Matching Source: https://academia.sh/en/courses/algorithms/brute-force-pattern-matching The definition of pattern matching in text, the sliding scan, character-comparison count, worst-case inputs, and behavior on real text. Graph algorithms worked on data with connections between elements. This topic moves to a different structure: **sequences of symbols in order** — text. The basic question of text processing is pattern matching, and this lesson builds the question itself along with its plainest solution. The next four lessons improve on the same problem with different ideas; the measure stays the same throughout: the number of character comparisons. #### The Problem **Pattern matching:** A text of length $n$ and a pattern of length $m$ are given; the positions at which the pattern occurs in the text are wanted. The question has three common forms, and their costs differ: - **First occurrence.** Stop as soon as one is found. - **All occurrences.** Continue to the end of the text. - **Occurrence count.** Count without storing positions. The same text and pattern are used throughout this topic: ```python text = "ABABDABACDABABCABAB" pattern = "ABABCABAB" ``` The pattern occurs once in the text, at index 10. The example is also well suited for testing the ideas of the following lessons, because the pattern itself contains internal repetition. #### The Sliding Scan The plainest solution is to place the pattern at every position of the text and compare it character by character. On a mismatch, the pattern is shifted one position to the right and comparison restarts from scratch. ```python def brute_force(text: str, pattern: str) -> tuple[list[int], int]: """(positions found, character-comparison count)""" n, m = len(text), len(pattern) positions: list[int] = [] count = 0 for shift in range(n - m + 1): j = 0 while j < m: count += 1 if text[shift + j] != pattern[j]: break j += 1 if j == m: positions.append(shift) return positions, count print(brute_force(text, pattern)) # ([10], 29) print(brute_force("ABABAB", "AB")) # ([0, 2, 4], 8) ``` The invariant is this: no position before `shift` contains a full match. Termination follows from the shift increasing by one on every turn. The algorithm is correct and uses no extra space. Its problem is its cost. #### Cost The outer loop runs $n - m + 1$ times, the inner loop at most $m$ times: $$ O\big((n - m + 1)\, m\big) = O(nm) $$ Reaching the worst case requires an input where a long prefix matches on every shift but the end does not. ```python bad_text = "A" * 30 + "B" bad_pattern = "A" * 10 + "B" print(brute_force(bad_text, bad_pattern)) # ([20], 231) print(len(bad_text), len(bad_pattern)) # 31 11 ``` On every shift, ten `A` characters match, the final character does not, and all the work is wasted. The comparison count approaches the product $(n - m + 1) \cdot m$: $21 \times 11 = 231$. Such inputs look artificial, but binary data, sequences over a small alphabet (genetic sequences, for instance), and logs carrying repetitive structure genuinely produce this behavior. #### Behavior on Real Text Natural language behaves differently: a mismatch typically shows up within the first few characters, and the inner loop breaks early. ```python long_text = ("the cost of searching for a pattern inside a text depends on " "how large the alphabet is and on repetition. ") * 10 for query in ("pattern", "cost", "zzz"): positions, count = brute_force(long_text, query) print(query, len(positions), count, len(long_text)) # pattern 10 1144 1060 # cost 10 1097 1060 # zzz 0 1058 1060 ``` The comparison count is a small multiple of the text length — nowhere near the multiplicative worst case. With an alphabet of size $\sigma$, the expected comparison count per shift is approximately $1/(1 - 1/\sigma)$; this value approaches 1 as the alphabet grows. The result echoes a warning from the algorithm-analysis lessons: **worst case and typical case are different questions.** Brute-force search is fast in practice on text with a large alphabet; what makes it a problem is that it silently drops to quadratic behavior on adversarial input. #### The Unit of Comparison Algorithms are defined over "characters," but in real text what that unit is turns out to be a choice, and the choice changes the result. The encoding lesson in the How Computers Work course separated three levels: the **byte**, the **code point**, and the **grapheme cluster** — the unit the user counts as a single letter. A pattern-matching routine has to state which of these it operates on. Byte-level search is the fastest, and it produces no false matches in multibyte encodings — the encoding guarantees that one character's bytes never appear in the middle of another character's bytes. The position found, however, is in bytes; a character position requires a conversion. Code-point-level search causes surprises with combined letters: two pieces of text that look identical can be written with different code-point sequences. In that case a **normalization** step is needed before the search. Case-insensitive search, in turn, depends on the language; case-folding rules are not the same in every language, and a single-character conversion is not guaranteed to always produce a single character. These distinctions do not change the algorithm, but they determine the cost and the correctness of the comparison operation. In this lesson and the following ones, the unit of comparison is taken to be a single code unit. #### The Information That Is Lost The algorithm's waste concentrates in a single point: **the comparisons made before a mismatch are forgotten.** When comparing the pattern `ABABC` against the text `ABABD…`, it is known that the first four characters matched. Brute force discards this and restarts one position to the right — even though the structure of the matched part could show that trying some of the shifts is unnecessary. The next three lessons use this information in three different ways: | Approach | Information used | |---|---| | Rabin–Karp | The hash value of the window; comparing numbers instead of characters | | Knuth–Morris–Pratt | The pattern's own prefix–suffix structure | | Boyer–Moore | The mismatched text character and matching from the end of the pattern | All three solve the same problem and produce the same result; what separates them is which information they precompute and use during the search. #### When It Is Enough Brute-force search has two advantages: it does no preprocessing and uses no extra space. This makes it the right choice when: - The pattern is short and the text is small; setup cost outweighs the gain. - Every search uses a different pattern; preprocessing would have to be paid again each time. - The alphabet is large and the text is natural language; typical behavior is already close to linear. By contrast, if the same pattern will be searched for many times, preprocessing methods stand out; if the same **text** will be queried many times, structures that preprocess the text do. This second path is the subject of the suffix-arrays lesson. #### Summary - Pattern matching finds the positions at which a given sequence occurs in a text; first occurrence, all occurrences, and counting have different costs. - Brute-force search compares from scratch on every shift; it uses no extra space and needs no preprocessing. - The worst case is $O(nm)$ and genuinely occurs on repetitive inputs over a small alphabet. - Because mismatches occur early in natural language, typical cost is close to linear. - The algorithm's waste is discarding the information gained before a mismatch. - The following methods use this information through a hash value, the pattern's prefix–suffix structure, or matching from the end. #### Next Step The first improvement idea is surprising: never compare characters at all. If every window of the text is reduced to a number and compared against the pattern's number, most positions are eliminated in a single operation. The next lesson builds the rolling hash idea, updated at constant cost from window to window, and how hash collisions are handled. ### Rabin–Karp Source: https://academia.sh/en/courses/algorithms/rabin-karp Pattern matching with a rolling hash, constant-cost window updates, collision verification, worst case, and its advantage in multi-pattern search. Brute-force search compared characters one by one in every window. This lesson's idea turns comparison into a completely different operation: reduce every window of the text to a **number** and compare numbers. Comparing numbers is a single operation. The problem is that computing each window's number takes $O(m)$ — as it stands, there is no gain at all. The solution is to **not compute the number from scratch.** #### Rolling Hash When a window shifts one character to the right, if the new hash value can be obtained from the old one with a constant number of operations, the method is called a **rolling hash**. The hash used treats characters as digits of a number base. For base $b$ and prime modulus $q$, the value of a window of length $m$ is: $$ H = \left(\sum_{i=0}^{m-1} s_i \cdot b^{\,m-1-i}\right) \bmod q $$ When the window shifts right, the contribution of the leftmost character is subtracted, the remainder is shifted one digit, and the new character is added: $$ H' = \big((H - s_{\text{left}} \cdot b^{\,m-1})\cdot b + s_{\text{new}}\big) \bmod q $$ Three operations, independent of length: the update is $O(1)$. #### Implementation ```python def rabin_karp(text: str, pattern: str, base: int = 256, modulus: int = 1_000_003) -> tuple[list[int], int, int]: """(positions, hash-match count, characters verified)""" n, m = len(text), len(pattern) if m > n: return [], 0, 0 power = pow(base, m - 1, modulus) # b^(m-1) mod q hash_pattern = hash_text = 0 for i in range(m): # first window and the pattern hash_pattern = (hash_pattern * base + ord(pattern[i])) % modulus hash_text = (hash_text * base + ord(text[i])) % modulus positions: list[int] = [] matches, verifications = 0, 0 for shift in range(n - m + 1): if hash_text == hash_pattern: # candidate: hashes equal matches += 1 verifications += m if text[shift:shift + m] == pattern: positions.append(shift) if shift < n - m: # roll the window hash_text = (hash_text - ord(text[shift]) * power) % modulus hash_text = (hash_text * base + ord(text[shift + m])) % modulus return positions, matches, verifications text = "ABABDABACDABABCABAB" pattern = "ABABCABAB" print(rabin_karp(text, pattern)) # ([10], 1, 9) print(rabin_karp("ABABAB", "AB")) # ([0, 2, 4], 3, 6) ``` Of the text's eleven windows, only one passes the hash test, and nine characters are read for verification. The difference is clear against the 29 comparisons brute force made on the same input. Because Python's remainder operation produces a non-negative result on negative numbers, intermediate values need no correction; in languages that use fixed-width integers, a modulus correction is added after the subtraction. The signed-arithmetic difference from the How Computers Work course can turn into a concrete bug here. #### Collision and Verification Hash equality does not **prove** that two sequences are equal. Different sequences can fall on the same value — the same collision concept from the Data Structures course. For this reason, every hash match is verified by character comparison. Without verification, the algorithm produces a wrong result. ```python # If the modulus is deliberately chosen small, collisions increase print(rabin_karp("ABABDABACDABABCABAB", "ABABCABAB", modulus=7)) # ([10], 4, 36) ``` With a small modulus, four windows pass the hash test, but only one is a real match; the other three are eliminated during verification. The result is still correct — the cost is the wasted character comparisons. This is the general pattern of hash-based methods: **the hash filters, verification decides.** #### Cost Expected cost is $O(n + m)$: each window takes constant work, and the collision probability is negligible once the modulus is chosen large enough. The worst case is $O(nm)$ and arises in two ways. The first is that there genuinely are a large number of matches (searching for `"AA"` inside `"AAAA…"`) — this is unavoidable, because the output itself is large. The second is text constructed to produce collisions against the chosen hash function; choosing the modulus at random turns this attack into a mere probability. | Criterion | Brute force | Rabin–Karp | |---|---|---| | Preprocessing | None | $O(m)$ | | Expected search | $O(nm)$ worst case | $O(n + m)$ | | Worst-case search | $O(nm)$ | $O(nm)$ | | Extra space | $O(1)$ | $O(1)$ | #### Choosing the Base and the Modulus Two parameters determine the method's behavior. The **base** should not be smaller than the alphabet size; if it is, distinct character sequences regularly fall on the same value. For byte sequences, 256 works; for small alphabets, a value equal to the alphabet size is enough. The **modulus** is chosen prime. A non-prime modulus that shares factors with the base piles hash values onto particular residues and increases collisions. The size of the modulus is a question of overflow: the intermediate product `hash * base` must not exceed the language's integer width. In sixty-four-bit arithmetic, keeping the modulus under roughly $2^{31}$ guarantees this. Python's unbounded integers remove this constraint, at the cost of higher operation cost for large values. The collision probability for a random modulus is approximately $m/q$ per window. If a stronger guarantee is needed, **two independent hashes** are used together; the probability of both colliding shrinks to the product of the two, and verification does almost no wasted work. #### The Real Advantage: Multiple Patterns The method's clearest gain shows up not in single-pattern search but in searching for **many patterns of the same length together**. The patterns' hash values are kept in a set; the text is scanned in a single pass, with one set lookup per window. ```python def multi_rabin_karp(text: str, patterns: list[str], base: int = 256, modulus: int = 1_000_003) -> dict[str, list[int]]: m = len(patterns[0]) if any(len(p) != m for p in patterns): raise ValueError("all patterns must have the same length") targets: dict[int, list[str]] = {} for p in patterns: h = 0 for character in p: h = (h * base + ord(character)) % modulus targets.setdefault(h, []).append(p) power = pow(base, m - 1, modulus) h = 0 for i in range(m): h = (h * base + ord(text[i])) % modulus result: dict[str, list[int]] = {p: [] for p in patterns} for shift in range(len(text) - m + 1): for candidate in targets.get(h, []): if text[shift:shift + m] == candidate: result[candidate].append(shift) if shift < len(text) - m: h = (h - ord(text[shift]) * power) % modulus h = (h * base + ord(text[shift + m])) % modulus return result print(multi_rabin_karp("ABABDABACDABABCABAB", ["ABAB", "BACD", "CABA"])) # {'ABAB': [0, 10, 15], 'BACD': [6], 'CABA': [14]} ``` Three patterns are found in a single pass over the text. For $k$ patterns, the cost is $O(n + km)$; searching for each pattern separately with brute force would be $O(knm)$. The same idea extends to two dimensions: rolling row hashes make it possible to search for a rectangular pattern inside an image. The rolling hash is also used in areas such as content-defined chunking — the same constant-cost window update, put to a different purpose. #### Summary - Rabin–Karp reduces windows to a hash value and turns comparison into number equality. - The rolling hash updates its value with a constant number of operations as the window shifts. - Hash equality is not proof; every candidate is verified by character comparison. - Expected cost is $O(n + m)$, worst case $O(nm)$; a random modulus protects against constructed inputs. - The real advantage is searching for many patterns of the same length in a single pass: $O(n + km)$. #### Next Step Rabin–Karp compressed the pattern's **content** into a number but never used its **structure**. Yet the overlap between the prefix and suffix of the pattern `ABABCABAB` tells us, at the moment of a mismatch, how many positions can safely be skipped. The next lesson computes this structure as a prefix function and builds a search that never backtracks in the text. ### Knuth–Morris–Pratt Source: https://academia.sh/en/courses/algorithms/knuth-morris-pratt The definition of the prefix function and its linear computation, search that never backtracks in the text, amortized cost analysis, and string periodicity. Brute-force search wasted effort by forgetting the matches made before a mismatch. Rabin–Karp reduced this waste with a hash but never used the pattern's **structure** at all. The idea of the Knuth–Morris–Pratt algorithm is this: if the matched part is already known, the pattern's own internal repetition tells us how many positions can safely be skipped. #### The Observation Consider comparing the pattern `ABABCABAB` against the text, where the first four characters (`ABAB`) matched and the fifth did not. It is known **for certain** that the text contains `ABAB` at that position. Brute force shifts by one position and tests the text's `BAB…` portion from scratch. Yet the `AB` prefix of `ABAB` is also its `AB` suffix; the search can therefore continue after shifting by two positions, without retesting the pattern's first two characters. The intermediate positions are not worth trying, because what characters are there is already known. The general rule: the longest piece that is **both a prefix and a suffix** of the matched prefix is kept, the rest is discarded. #### The Prefix Function The **prefix function** $\pi$ gives, for every prefix of the pattern, "the length of the longest piece that is both a proper prefix and a suffix." "Proper" here means the piece cannot be the whole prefix itself. ```python def prefix_function(pattern: str) -> list[int]: """pi[i]: the longest proper prefix-suffix length of pattern[0..i].""" pi = [0] * len(pattern) k = 0 for i in range(1, len(pattern)): while k > 0 and pattern[i] != pattern[k]: k = pi[k - 1] # fall back to a shorter candidate prefix if pattern[i] == pattern[k]: k += 1 pi[i] = k return pi print(prefix_function("ABABCABAB")) # [0, 0, 1, 2, 0, 1, 2, 3, 4] print(prefix_function("AABAACAABAA")) # [0, 1, 0, 1, 2, 0, 1, 2, 3, 4, 5] print(prefix_function("ABCDE")) # [0, 0, 0, 0, 0] ``` The values read directly: the longest prefix–suffix overlap of the entire pattern `ABABCABAB` is 4 (`ABAB`); for the `ABAB` piece up to its fourth character it is 2 (`AB`); for `ABCDE`, which contains no repetition at all, every value is zero. The computation itself is searching the pattern within itself: the variable `k` holds the length of the prefix matched so far and falls back to a shorter candidate on a mismatch. The cost is $O(m)$ — the reasoning is the same as in the search, and is given in the next section. #### The Search The search applies the same fallback logic to the text. The text cursor **never moves backward**; only the pattern cursor falls back. ```python def kmp(text: str, pattern: str) -> tuple[list[int], int]: """(positions, character-comparison count)""" pi = prefix_function(pattern) positions: list[int] = [] k = 0 count = 0 for i, character in enumerate(text): while k > 0 and character != pattern[k]: count += 1 k = pi[k - 1] count += 1 if character == pattern[k]: k += 1 if k == len(pattern): positions.append(i - len(pattern) + 1) k = pi[k - 1] # do not miss an overlapping next occurrence return positions, count text = "ABABDABACDABABCABAB" pattern = "ABABCABAB" print(kmp(text, pattern)) # ([10], 23) print(kmp("ABABAB", "AB")) # ([0, 2, 4], 6) print(kmp("A" * 30 + "B", "A" * 10 + "B")) # ([20], 51) ``` The last line is decisive: on the input where brute force made 231 comparisons, KMP makes 51. The quadratic behavior has disappeared entirely. Once a match is found, the assignment `k = pi[k-1]` ensures overlapping occurrences are not missed. Searching for `ABAB` inside `ABABAB` finds both position 0 and position 2. #### Cost Preprocessing is $O(m)$, search is $O(n)$, total $O(n + m)$ — in the **worst case**. Extra space is $O(m)$ (the prefix-function table). The reasoning is amortized; the total-cost method from the Method for Computing Complexity lesson applies here directly. The variable `k` increases by at most one on every turn; over $n$ turns, its total increase is at most $n$. Every turn of the inner loop decreases `k` by at least one, and `k` never goes negative. The inner loop can therefore run at most $n$ times in total. Although the inner loop looks like $O(m)$ in isolation, its total cost across the whole search is linear. | Criterion | Brute force | Rabin–Karp | KMP | |---|---|---|---| | Preprocessing | None | $O(m)$ | $O(m)$ | | Worst-case search | $O(nm)$ | $O(nm)$ | $O(n)$ | | Extra space | $O(1)$ | $O(1)$ | $O(m)$ | | Backtracks in text | Yes | No | No | The last row produces a practical consequence: because the text cursor never moves backward, the algorithm can run over a **stream** that is not entirely in memory. Characters are processed as they arrive; no rewinding is needed. #### The Automaton View The prefix function is, in fact, a compressed form of a **finite automaton**. Its states hold the information "how many characters of the pattern have matched so far"; a transition is defined for every character, and the final state signals a match. If the transitions are precomputed, the fallback loop disappears from the search as well: exactly one table lookup is made for every text character. ```python def automaton(pattern: str, alphabet: str) -> list[dict[str, int]]: pi = prefix_function(pattern) m = len(pattern) transition: list[dict[str, int]] = [{} for _ in range(m + 1)] for state in range(m + 1): for character in alphabet: if state < m and character == pattern[state]: transition[state][character] = state + 1 # advance elif state == 0: transition[state][character] = 0 # back to start else: transition[state][character] = transition[pi[state - 1]][character] return transition def search_with_automaton(text: str, pattern: str, alphabet: str) -> list[int]: transition = automaton(pattern, alphabet) m, state = len(pattern), 0 positions: list[int] = [] for i, character in enumerate(text): state = transition[state][character] if state == m: positions.append(i - m + 1) return positions print(search_with_automaton("ABABDABACDABABCABAB", "ABABCABAB", "ABCD")) # [10] ``` The cost is in memory: the table takes $O(m\sigma)$ space, and this is a serious cost when the alphabet is large. The prefix function, by contrast, takes $O(m)$ space and produces the same behavior amortized. The choice between the two approaches is made by looking at alphabet size and search frequency. #### Periodicity The prefix function directly gives one more piece of information besides the search: a string's **smallest period**. For a string of length $m$, the value $p = m - \pi[m-1]$ is the smallest period length. If $m$ is exactly divisible by $p$, the string consists of repetitions of that piece. ```python def smallest_period(string: str) -> tuple[int, bool]: pi = prefix_function(string) p = len(string) - pi[-1] return p, len(string) % p == 0 for example in ("ABABAB", "ABCABCABC", "ABCD", "AAAA"): print(example, smallest_period(example)) # ABABAB (2, True) # ABCABCABC (3, True) # ABCD (4, True) # AAAA (1, True) ``` For `ABCD` the period is the length itself: there is no repetition. This computation is used in compression and in string-equivalence questions; the same table serves two different purposes. #### Summary - KMP uses the prefix–suffix overlap of the matched prefix to determine how many positions can be skipped on a mismatch. - The prefix function gives, for every prefix, the longest proper prefix–suffix length, and is computed in $O(m)$. - In the search, the text cursor never moves backward; only the pattern cursor falls back. - Total cost is $O(n + m)$; the reasoning is amortized, bounding the total increase of the variable `k`. - The absence of backtracking in the text makes the algorithm suitable for stream data. - The same table also gives a string's smallest period. #### Next Step KMP matches the pattern from start to end and looks at every text character at least once. The next lesson takes up an approach that matches in the opposite direction: comparison starting from the **end** of the pattern makes it possible to skip over some text characters **without ever looking at them** on a mismatch, and produces sublinear behavior in practice. ### Boyer–Moore Source: https://academia.sh/en/courses/algorithms/boyer-moore Matching from the end, the bad-character and good-suffix rules, the Horspool simplification, sublinear behavior, and a measured comparison of four algorithms. KMP looked at every text character at least once; this looks like a lower bound on linear cost. The Boyer–Moore family breaks this intuition: it is possible to produce the correct result **without ever looking** at some characters. The idea comes from a change of direction — the pattern is matched from the end toward the start. #### Why Matching from the End Pays Off The pattern is placed over a window of the text, and comparison starts from the **last** character. If the mismatch occurs at the very end, the text character at that point determines how far the pattern can be shifted. If the text character **does not occur at all** in the pattern, the pattern can be shifted entirely past it: a single comparison eliminates $m$ positions. The characters in between are never looked at. If it does occur in the pattern, the pattern is shifted just far enough to align its rightmost occurrence of that character with the text. This is the **bad-character rule**. #### The Shift Table The rule is applied with a simple table derived from the pattern: for each character, its distance from the end of the pattern. ```python def shift_table(pattern: str) -> dict[str, int]: """A character's distance from the end of the pattern; the last character is excluded.""" m = len(pattern) return {pattern[i]: m - 1 - i for i in range(m - 1)} print(shift_table("ABABCABAB")) # {'A': 1, 'B': 2, 'C': 4} ``` The table is built from `m - 1` characters; the last character is left out, because the shift must always be at least one. For a character not in the table, the shift is $m$. Values are computed from the **rightmost** occurrence in the pattern: if the same character occurs more than once, the last assignment in the dictionary remains, and that corresponds to the rightmost position. #### The Horspool Variant The short, widely used simplification of Boyer–Moore bases the shift not on the mismatching character but on the **last character of the window**. ```python def horspool(text: str, pattern: str) -> tuple[list[int], int]: """(positions, character-comparison count)""" n, m = len(text), len(pattern) if m > n: return [], 0 table = shift_table(pattern) positions: list[int] = [] shift, count = 0, 0 while shift <= n - m: j = m - 1 while j >= 0: # compare from end to start count += 1 if text[shift + j] != pattern[j]: break j -= 1 if j < 0: positions.append(shift) shift += 1 else: last = text[shift + m - 1] shift += table.get(last, m) # not in table: skip a full pattern length return positions, count text = "ABABDABACDABABCABAB" pattern = "ABABCABAB" print(horspool(text, pattern)) # ([10], 20) print(horspool("ABABAB", "AB")) # ([0, 2, 4], 8) print(horspool("aaa", "b")) # ([], 3) ``` Because the shift is always at least 1, termination is guaranteed. Correctness rests on the rule guaranteeing that the skipped positions **cannot** contain a match: the shift goes only as far as the nearest alignment at which the window's last character could occur in the pattern. #### The Measured Difference Comparing all four algorithms on the same inputs makes the difference in direction visible in numbers. ```python # brute_force and kmp: the implementations from the previous two lessons, brought # in here so the block can run on its own def brute_force(text: str, pattern: str) -> tuple[list[int], int]: """(positions found, character-comparison count)""" n, m = len(text), len(pattern) positions: list[int] = [] count = 0 for shift in range(n - m + 1): j = 0 while j < m: count += 1 if text[shift + j] != pattern[j]: break j += 1 if j == m: positions.append(shift) return positions, count def prefix_function(pattern: str) -> list[int]: """pi[i]: the longest proper prefix-suffix length of pattern[0..i].""" pi = [0] * len(pattern) k = 0 for i in range(1, len(pattern)): while k > 0 and pattern[i] != pattern[k]: k = pi[k - 1] # fall back to a shorter candidate prefix if pattern[i] == pattern[k]: k += 1 pi[i] = k return pi def kmp(text: str, pattern: str) -> tuple[list[int], int]: """(positions, character-comparison count)""" pi = prefix_function(pattern) positions: list[int] = [] k = 0 count = 0 for i, character in enumerate(text): while k > 0 and character != pattern[k]: count += 1 k = pi[k - 1] count += 1 if character == pattern[k]: k += 1 if k == len(pattern): positions.append(i - len(pattern) + 1) k = pi[k - 1] # do not miss an overlapping next occurrence return positions, count long_text = ("the cost of searching for a pattern inside a text depends on " "how large the alphabet is and on repetition. ") * 10 for query in ("pattern", "repetition", "zzzzz"): print(query, brute_force(long_text, query)[1], kmp(long_text, query)[1], horspool(long_text, query)[1]) # pattern 1144 1090 250 # repetition 1181 1100 260 # zzzzz 1056 1060 212 # ← text length: 1060 ``` Horspool makes **fewer** comparisons than the text's length: 250 to 260 on a 1060-character text, well under the total. As the pattern grows longer, the count drops further, because a larger step is taken on every failed attempt. This sublinear behavior is not a contradiction: the algorithm does not look at every character of the text. Showing that the pattern is absent does not require reading the entire text. The expected comparison count approaches $n/m$ as the alphabet size $\sigma$ grows. Because natural language and large alphabets satisfy this condition, matching from the end is the typical choice of text-search tools. #### Worst Case and the Good-Suffix Rule With the bad-character rule alone, the worst case stays $O(nm)$. On small-alphabet, repetitive inputs, the shifts shrink. ```python print(horspool("A" * 30 + "B", "A" * 10 + "B")[1]) # 31 print(brute_force("A" * 30 + "B", "A" * 10 + "B")[1]) # 231 ``` On this input the result is good, because the mismatch shows up on the first comparison. The reverse construction — a pattern such as `"BAAAAAAAAA"` inside `"A"*30` — brings the shifts down to one. Full Boyer–Moore adds the **good-suffix rule** to the bad-character rule: if the matched suffix occurs elsewhere in the pattern, the pattern is aligned to that occurrence; if it does not, a prefix of the suffix is aligned to the start of the pattern. Whichever rule proposes the larger shift is chosen. The good-suffix table is built in $O(m)$, in a manner similar to KMP's prefix function. With an additional technique (a rule that prevents already-matched regions from being recompared), the worst case can be brought down to $O(n)$. #### Looking One Past the Window Another variant in the same family bases the shift not on the window's **last character** but on the character **immediately after** the window. Because that character will remain inside the pattern at the next alignment, $m+1$ positions can be skipped at once if it does not occur in the pattern at all. ```python def quick_search(text: str, pattern: str) -> tuple[list[int], int]: n, m = len(text), len(pattern) if m > n: return [], 0 table = {pattern[i]: m - i for i in range(m)} # every character is in the table positions: list[int] = [] shift, count = 0, 0 while shift <= n - m: j = 0 while j < m: count += 1 if text[shift + j] != pattern[j]: break j += 1 if j == m: positions.append(shift) if shift + m >= n: break shift += table.get(text[shift + m], m + 1) return positions, count print(quick_search(text, pattern)) # ([10], 14) print(quick_search(long_text, "repetition")[1]) # 228 ``` Here the comparison direction is start to end; the gain comes entirely from the shift rule. The table covering every pattern character, and the shift being able to reach $m+1$, shortens the implementation while producing large steps in practice. #### Where the Four Methods Stand | Criterion | Brute force | Rabin–Karp | KMP | Boyer–Moore | |---|---|---|---|---| | Preprocessing | None | $O(m)$ | $O(m)$ | $O(m + \sigma)$ | | Expected | $O(n)$ (large alphabet) | $O(n + m)$ | $O(n + m)$ | close to $O(n/m)$ | | Worst case | $O(nm)$ | $O(nm)$ | $O(n + m)$ | $O(n)$ (full form) | | Extra space | $O(1)$ | $O(1)$ | $O(m)$ | $O(m + \sigma)$ | | Stream data | Suitable | Suitable | Suitable | Not suitable | The last row is the cost of matching from the end: because the algorithm moves backward within the window, a single forward pass over the text is not enough. The choice criterion is this: **if the alphabet is large and the pattern is long**, Boyer–Moore; **if a worst-case guarantee or stream processing is needed**, KMP; **if many patterns are searched for at once**, Rabin–Karp; for **short text and a one-time search**, brute force. #### Summary - The Boyer–Moore family matches the pattern from end to start; this makes it possible to skip some text characters without ever looking at them. - The bad-character rule aligns to the rightmost occurrence of the mismatching text character in the pattern; if it does not occur, a full pattern length is skipped. - The Horspool variant bases the shift on the window's last character and works with a single table. - The expected comparison count approaches $n/m$ as the alphabet grows; measured, it drops below the length of the text. - Adding the good-suffix rule brings the worst case down to linear. - Matching from the end does not suit stream data; it moves backward within the window. #### Next Step All four algorithms preprocessed the **pattern**; the text was scanned from scratch on every search. If thousands of queries will be made against the same text, the balance reverses: it becomes cheaper to preprocess the text once and answer every query at logarithmic cost. The next lesson takes up the structures that organize all of a text's suffixes — the suffix array and the suffix tree. ### Suffix Arrays and Trees Source: https://academia.sh/en/courses/algorithms/suffix-arrays-and-trees Structures that preprocess text, building a suffix array and querying it with binary search, the LCP array, comparison with the suffix tree, and applications. The previous four algorithms preprocessed the **pattern**; the text was scanned from scratch on every search. This is the right balance for one-time searches. The balance reverses when thousands of queries are made against the same text: the text can be preprocessed once, and queries answered at a cost that depends not on the text's length but on the **pattern's**. This lesson builds those structures. #### The Suffix Array All of a text's suffixes are sorted, and only their **starting positions** are stored. The resulting array of integers is called a **suffix array**. ```python def suffix_array(text: str) -> list[int]: """Starting positions that arrange the suffixes in lexicographic order.""" return sorted(range(len(text)), key=lambda i: text[i:]) text = "banana" sa = suffix_array(text) print(sa) # [5, 3, 1, 0, 4, 2] print([text[i:] for i in sa]) # ['a', 'ana', 'anana', 'banana', 'na', 'nana'] ``` The structure holds only $n$ integers; the text itself is stored once. The memory cost is far lower than storing the suffixes separately. The construction above is $O(n^2 \log n)$, because it reads $O(n)$ characters per comparison, and it is meant only to illustrate the idea. A suffix array is built in $O(n \log n)$ with the method that doubles the compared length at each round, and in $O(n)$ with more advanced methods. #### Query Because the suffixes are sorted, the suffixes that **start with** the pattern occupy a contiguous range in the array. Binary search gives the boundaries of that range. ```python def match_range(text: str, sa: list[int], pattern: str) -> tuple[int, int]: """The [start, end) range in the suffix array of suffixes starting with pattern.""" m = len(pattern) lo, hi = 0, len(sa) while lo < hi: # lower bound mid = (lo + hi) // 2 if text[sa[mid]:sa[mid] + m] < pattern: lo = mid + 1 else: hi = mid start = lo lo, hi = start, len(sa) while lo < hi: # upper bound mid = (lo + hi) // 2 if text[sa[mid]:sa[mid] + m] <= pattern: lo = mid + 1 else: hi = mid return start, lo long_text = "ABABDABACDABABCABAB" long_sa = suffix_array(long_text) start, end = match_range(long_text, long_sa, "ABAB") print(end - start, sorted(long_sa[start:end])) # 3 [0, 10, 15] start, end = match_range(long_text, long_sa, "ZZ") print(end - start) # 0 ``` Every step of the binary search compares up to $m$ characters; query cost is $O(m \log n)$. The occurrence **count**, on the other hand, is read from the width of the range in a single operation — finding how many times a pattern occurs does not require scanning the text. Comparing the two costs makes the trade-off visible: KMP pays $O(n + m)$ on every query; the suffix array pays $O(n \log n)$ once, then answers every query at $O(m \log n)$. The second path wins as the number of queries grows — the text-side counterpart of the preprocessing pattern from the Time and Space Trade-off lesson. #### The Longest Common Prefix Array The suffix array is incomplete on its own; knowing the overlap between neighboring suffixes answers many more questions. The **LCP array** holds the length of the longest common prefix of two consecutive suffixes in the sorted order. Kasai's method computes it in $O(n)$. ```python def lcp_array(text: str, sa: list[int]) -> list[int]: """lcp[k]: the common-prefix length of the suffixes sa[k-1] and sa[k].""" n = len(text) rank = [0] * n for k, i in enumerate(sa): rank[i] = k lcp = [0] * n h = 0 for i in range(n): if rank[i] > 0: j = sa[rank[i] - 1] while i + h < n and j + h < n and text[i + h] == text[j + h]: h += 1 lcp[rank[i]] = h if h: h -= 1 # the next suffix carries at least h-1 common prefix else: h = 0 return lcp print(lcp_array("banana", sa)) # [0, 1, 3, 0, 0, 2] ``` The array's largest value gives the **longest piece that occurs twice** in the text. ```python def longest_repeat(text: str) -> str: sa = suffix_array(text) lcp = lcp_array(text, sa) k = max(range(len(lcp)), key=lambda i: lcp[i]) return text[sa[k]:sa[k] + lcp[k]] print(longest_repeat("banana")) # ana print(longest_repeat("ABABDABACDABABCABAB")) # ABAB ``` The same structure answers other questions as well: the longest common piece of two texts (by concatenating them and treating them as one), the number of distinct substrings, and repeat detection in compression. #### The Suffix Tree A **suffix tree** is a compressed trie containing all of a text's suffixes: chains of single-child nodes are merged, and edges represent subranges of the text. It carries the same information as the suffix array, arranged differently: | Criterion | Suffix array | Suffix tree | |---|---|---| | Construction | $O(n)$ (advanced methods) | $O(n)$ | | Query | $O(m \log n)$ | $O(m)$ | | Memory constant | Small ($n$ integers) | Large (nodes and pointers) | | Implementation | Simple | Complex | The logarithmic factor in query cost can also be removed by adding LCP information to the suffix array. In practice the suffix array is preferred: its memory constant is small and its code is easier to check. The suffix tree stands out in theoretical analyses that need the tree structure itself, and in certain specialized queries. A third structure in the same family is the **suffix automaton**: the smallest automaton that recognizes all of a text's substrings, and it directly answers questions such as counting distinct substrings. #### Where It Is Used Preprocessed text structures show up wherever the text is fixed and queries are numerous: - **Full-text indexing.** Search over a document collection; scanning the text per query does not scale. - **Bioinformatics.** Genetic sequences are long, the alphabet is small, and thousands of queries are made against the same sequence. - **Duplicate code and content detection.** Through longest-common-piece queries. - **Compression.** Finding repeated pieces; the Burrows–Wheeler transform rests directly on suffix sorting. The common criterion is the same: **once preprocessing cost is divided by the number of queries, does the gain remain?** This question was asked for sublinear classes in the Reading Complexity Classes lesson; here its answer turns into a concrete choice of data structure. #### Summary - A suffix array is the starting positions that arrange all of a text's suffixes in lexicographic order, and it takes up $n$ integers. - Suffixes starting with a pattern occupy a contiguous range; binary search answers a query in $O(m \log n)$, and the occurrence count is given by the range's width. - The LCP array holds the common-prefix length of consecutive suffixes and is computed in $O(n)$; its largest value gives the longest repeated piece. - The suffix tree arranges the same information as a tree; its query is $O(m)$, but its memory constant and implementation complexity are high. - The choice of structure is decided by dividing preprocessing cost by the number of queries. #### Next Step The final question of text algorithms differs from search: storing the same information in **less space**. The next lesson builds the Huffman method, which produces variable-length codes based on character frequencies, and shows why a greedy choice yields the optimal code. ### Huffman Coding Source: https://academia.sh/en/courses/algorithms/huffman-coding Variable-length prefix-free codes, greedy tree construction, the optimality argument, the entropy bound, and the method's limits. The final question of text algorithms differs from search: storing the same information in **less space**. Fixed-length coding assigns an equal number of bits to every symbol; the character encodings in the How Computers Work course followed this scheme. Symbols, however, do not occur with equal frequency. Giving a short code to a frequent symbol and a long code to a rare one lowers the total length. #### Prefix-Free Codes Variable length creates an ambiguity: if `A → 0` and `B → 01` are assigned, the sequence `001` can be read as the start of either `AB` or `AA…`. The solution is a **prefix-free code**: no symbol's code may be the prefix of another symbol's code. Such a code decodes unambiguously — as soon as the bits read so far match a code, that symbol is settled. Prefix-free codes correspond exactly to binary trees: symbols sit at the leaves, and a code is the sequence of bits (left 0, right 1) on the path from the root to a leaf. The condition of stopping at a leaf is exactly the prefix-free condition. A symbol's code length is the depth of its leaf. The goal is to minimize the weighted sum of depths: $$ \text{cost} = \sum_{i} f_i \cdot d_i $$ Here $f_i$ is the symbol's frequency and $d_i$ is the depth of its leaf. #### Greedy Construction The Huffman method builds the tree **from the leaves toward the root**: the two rarest symbols are merged and treated as a single node, and the process continues until a single node remains. The intuition is this: the two rarest symbols deserve the deepest leaves; merging them is the step that increases the cost the least. ```python import heapq from collections import Counter def huffman_codes(frequencies: dict[str, int]) -> dict[str, str]: """Symbol → binary code mapping.""" if len(frequencies) == 1: # special case: a single symbol return {next(iter(frequencies)): "0"} counter = 0 heap: list[tuple[int, int, dict[str, str]]] = [] for symbol, f in sorted(frequencies.items()): # fixed order: the heap is unstable on ties heapq.heappush(heap, (f, counter, {symbol: ""})) counter += 1 while len(heap) > 1: f1, _, left = heapq.heappop(heap) # the two rarest nodes f2, _, right = heapq.heappop(heap) merged = {s: "0" + k for s, k in left.items()} merged.update({s: "1" + k for s, k in right.items()}) heapq.heappush(heap, (f1 + f2, counter, merged)) counter += 1 return heap[0][2] text = "ABRACADABRA" frequencies = dict(Counter(text)) print(dict(sorted(frequencies.items()))) # {'A': 5, 'B': 2, 'C': 1, 'D': 1, 'R': 2} code = huffman_codes(frequencies) print(dict(sorted(code.items()))) # {'A': '0', 'B': '110', 'C': '100', 'D': '101', 'R': '111'} ``` The most frequent symbol, `A`, is coded with one bit; the rarest, `C` and `D`, with three. No code is the prefix of another. The third field placed in the heap (`counter`) makes the ordering deterministic on ties. Without it, the code could vary from run to run on equal frequencies; because the party decoding the compressed data must build the same tree, this would be an unwanted ambiguity. #### Gain and Decoding ```python import math def encode(text: str, code: dict[str, str]) -> str: return "".join(code[character] for character in text) def decode(bits: str, code: dict[str, str]) -> str: reverse = {v: k for k, v in code.items()} result: list[str] = [] buffer = "" for bit in bits: buffer += bit if buffer in reverse: # prefix-free, so the first match is certain result.append(reverse[buffer]) buffer = "" return "".join(result) bits = encode(text, code) fixed_length = len(text) * math.ceil(math.log2(len(frequencies))) print(len(bits), fixed_length) # 23 33 print(decode(bits, code) == text) # True ``` Five distinct symbols require three bits at fixed length: 33 bits. The Huffman code stores the same text in 23 bits — roughly a third less. Decoding is a direct consequence of the prefix-free property: a decision is made the moment the accumulated bit sequence matches a code, with no backtracking required. #### Optimality Among methods that **assign a code per symbol**, the Huffman code gives the smallest total length. The argument rests on two observations. **First:** In an optimal tree, the two rarest symbols can be placed at the deepest level, as siblings. If they are not, swapping them does not increase the cost — the same exchange argument as in the minimum-spanning-tree lesson. **Second:** Once two symbols are merged and counted as a single symbol, the optimal solution of the smaller problem gives the optimal solution of the original problem. Together, the two show that the greedy choice is safe at every step. Construction cost is $O(k \log k)$ because of the priority queue, where $k$ is the number of distinct symbols. #### The Entropy Bound There is a limit to how much improvement is possible. With symbol probabilities $p_i$, the **entropy** $$ H = -\sum_i p_i \log_2 p_i $$ is the lower bound on the average number of bits per symbol. The Huffman code operates close to this bound: its average length lies between $H$ and $H + 1$. ```python n = len(text) H = -sum((f / n) * math.log2(f / n) for f in frequencies.values()) print(round(H, 3), round(len(bits) / n, 3)) # 2.04 2.091 ``` The measured average, 2.091 bits, sits just above the theoretical lower bound of 2.04 bits. The gap comes from code lengths having to be integers; a symbol cannot be given 1.5 bits. Crossing this bound is only possible by changing the assumption — much as the lower bound on comparison-based sorting is crossed by using the structure of keys. Methods that code symbols in groups rather than one at a time approach the fractional-bit cost; methods that dictionary-encode repeated pieces drop the assumption of symbol independence and exploit repetition in the text instead. The second is directly related to the suffix structures from the previous lesson. #### Limits and Implementation Details **A frequency table is required.** Encoding needs two passes: frequencies are counted first, then encoding happens. The table is also stored so the decoder can rebuild the tree; on short text this overhead can eat up the gain. **Adaptive variants** update the table as the stream progresses and work in a single pass; in exchange, the encoder and decoder must follow exactly the same update rule. **Symbol independence is assumed.** The method does not use a symbol's relationship to the one before it. In natural language this relationship is strong; for this reason Huffman is generally used not on its own but after a stage that eliminates repetition first. **It is lossless.** Decoded data is identical, bit for bit, to the original. The lossy methods used for images and audio belong to a different family and are outside this course. #### Summary - Prefix-free codes decode unambiguously and correspond exactly to binary trees; code length is the depth of the leaf. - The Huffman method builds the tree from the leaves to the root by merging the two rarest nodes; its cost is $O(k \log k)$. - Its optimality rests on an exchange argument showing the two rarest symbols can be made siblings. - Average code length lies between entropy and entropy plus one; the gap comes from bit counts having to be integers. - Storing the frequency table, the assumption of symbol independence, and the two-pass structure are the method's main limits. #### Course Wrap-Up The Algorithms course began with a measure and ended with application. First, the cost of a solution was defined: operation counting, asymptotic notation, complexity classes, the algorithm-analysis method, and the time–space trade-off. The same measure was then used across three areas — searching and sorting, graph algorithms, text algorithms. A handful of recurring ideas turn the course into a single system: - **Thinking in lower bounds.** Comparison-based search $\Omega(\log n)$, comparison-based sorting $\Omega(n \log n)$, entropy $H$: every problem has a floor that cannot be crossed, and that floor is crossed only by changing the assumption. - **Proving a greedy choice.** Dijkstra, Prim, Kruskal, and Huffman share the same pattern: the choice is shown safe with an exchange argument. - **Divide and conquer.** Merge sort, quicksort, binary search, and counting inverted pairs all arise from the same relation. - **The preprocessing trade-off.** Binary search, the suffix array, the KMP table, and hash-based methods are different forms of the same calculation: pay once, gain many times. The next course, **Operating System Concepts**, takes up the layer these algorithms run on: processes, concurrency, memory management, and file systems. The analysis tools built here will be used directly in topics such as scheduling algorithms, page replacement, and deadlock detection.