Anshid Aboobacker

Module I — Introduction to Algorithms

← Back to Data Structures and Algorithms

Course: MAT5EJ302(1) — Data Structures and Algorithms
Hours: 12 | Textbook Sections: 0.2, 0.3, 1.1, 1.2, 1.3 (Dasgupta et al.)

1. What Is an Algorithm?

An algorithm is a finite, step-by-step procedure that solves a well-defined computational problem. It takes an input and produces an output. The central questions in this course are:

  • Correctness: Does the algorithm always produce the right answer?
  • Efficiency: How fast does it run, and how much memory does it use?

The efficiency question is what separates a practically useful algorithm from one that is theoretically correct but takes millions of years to run on a real input.

The Three Standard Questions. Dasgupta, Papadimitriou and Vazirani’s textbook asks the same three questions of every algorithm it studies, and we will do the same throughout this module:

  1. Is it correct?
  2. How much time does it take, as a function of the input size?
  3. Can we do better?

Watch for this pattern recurring below: naive recursive Fibonacci prompts “can we do better?”, answered by fib2; grade-school multiplication prompts it again, answered by Karatsuba’s algorithm in Module II; and Euclid’s algorithm is itself the answer to “can we do better than factoring?” for computing GCDs.

2. Computing Fibonacci Numbers

The Fibonacci sequence is defined as:

\[F_0 = 0 \\ F_1 = 1 \\ F_n = F_{n-1} + F_{n-2} \quad \text{for } n \geq 2\]

The first few values: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, …

This sequence is a perfect testing ground for comparing algorithm efficiency because the same problem can be solved with vastly different running times.

2.1 Algorithm 1 — Naive Recursion (Exponential Time)

function fib1(n)
    if n = 0: return 0
    if n = 1: return 1
    return fib1(n-1) + fib1(n-2)

How it works: Directly translates the mathematical definition into code.

The problem: Consider computing fib1(5). It calls fib1(4) and fib1(3). fib1(4) then calls fib1(3) and fib1(2). Notice that fib1(3) is computed twice. In general, the same subproblems are recomputed exponentially many times.

Time complexity: Let $T(n)$ be the number of additions performed.

  • $T(0) = T(1) = 0$
  • $T(n) = T(n-1) + T(n-2) + 1$

This satisfies the same recurrence as Fibonacci itself, so $T(n) \approx \varphi^n$ where $\varphi = \frac{1+\sqrt{5}}{2} \approx 1.618$ (the golden ratio). This is exponential in $n$.

Concretely: computing $F_{100}$ would require roughly $\varphi^{100} \approx 10^{21}$ operations — more than a trillion operations per second for billions of years.

2.2 A Stepping Stone — Memoisation (Polynomial Time)

The key observation: the naive algorithm does redundant work. Fix this by storing results once computed.

Naming note. We deliberately do not call this algorithm fib2. In Dasgupta, Papadimitriou and Vazirani’s own textbook, fib2 refers to a different algorithm — the iterative, bottom-up array method presented next (§2.3). The book’s main chapter text never gives memoisation a name of its own at all; we introduce it here anyway, under the neutral name memoFib, because it is a useful stepping stone between the naive recursive idea and the book’s own fib2.

function memoFib(n, memo)
    if n in memo: return memo[n]
    if n = 0: return 0
    if n = 1: return 1
    memo[n] = memoFib(n-1, memo) + memoFib(n-2, memo)
    return memo[n]

How it works: Before computing $F_n$, check if it was already computed. Each value is computed exactly once.

Time complexity: $\mathcal{O}(n)$ additions — a dramatic improvement from exponential.

2.3 Algorithm 2 — fib2: Iterative (Polynomial Time, Better)

This is the book’s own fib2 — the second of the two Fibonacci algorithms Dasgupta, Papadimitriou and Vazirani actually present in their main text. Even simpler than memoisation: compute from the bottom up.

function fib2(n)
    if n = 0: return 0
    a = 0, b = 1
    for i = 2 to n:
        a, b = b, a + b
    return b

Time complexity: $\mathcal{O}(n)$ arithmetic operations (additions), $\mathcal{O}(1)$ space (only three variables needed). This counts additions, not bit operations — see the note at the end of §2.5 for why those differ.

2.4 Algorithm 3 — fib3: Matrix Exponentiation

Can we beat $\mathcal{O}(n)$? Surprisingly, yes — if we count arithmetic operations rather than bit operations. This is the book’s own fib3, and unlike fib1 and fib2, it appears only as Exercise 0.4 in the textbook, never in the main chapter body.

The recurrence can be written as a matrix equation. With $X = \begin{pmatrix}0 & 1\1 & 1\end{pmatrix}$, one can check directly that

\[\begin{pmatrix}F_n\\F_{n+1}\end{pmatrix} = X^n \begin{pmatrix}F_0\\F_1\end{pmatrix}.\]

So computing $F_n$ reduces to computing the matrix power $X^n$. Just as with ModExp (§5.3), we compute $X^n$ by repeated squaring rather than $n-1$ successive multiplications by $X$:

function fib3(n)
    if n = 0: return 0
    P = MatrixPower(X, n)     # repeated squaring, O(log n) matrix multiplications
    return P[0][1]            # = F_n

Time complexity: $\mathcal{O}(\log n)$ arithmetic operations — exponentially fewer than fib2’s $n-1$ additions. But this is not automatically fewer bit operations: $F_n$ itself is about $n$ bits long, so multiplying two such numbers isn’t a constant-time step, exactly the same subtlety flagged for fib1 and fib2 below. Whether fib3 truly beats fib2 in total bit operations depends on how fast large numbers can be multiplied (Module II).

2.5 Comparison

Algorithm Time Complexity Space
fib1 (naive recursion) $\mathcal{O}(\varphi^n) \approx \mathcal{O}(1.618^n)$ — exponential $\mathcal{O}(n)$ call stack
memoFib (memoisation, bridge step) $\mathcal{O}(n)$ — polynomial $\mathcal{O}(n)$
fib2 (iterative) $\mathcal{O}(n)$ — polynomial $\mathcal{O}(1)$
fib3 (matrix exponentiation) $\mathcal{O}(\log n)$ arithmetic ops $\mathcal{O}(1)$ matrices

Key lesson: The mathematical definition of a problem does not dictate the algorithm. Thinking carefully about how to compute can reduce the running time from exponential to polynomial — and sometimes further still.

Note: Strictly speaking, Fibonacci numbers themselves grow exponentially ($F_n \approx \varphi^n/\sqrt{5}$), so each $F_n$ has about $n$ bits, meaning the addition itself is not $\mathcal{O}(1)$ for very large $n$. Concretely: the addition at step $i$ of fib2 costs $\mathcal{O}(i)$ bit operations (since $F_i$ has $\mathcal{O}(i)$ bits), so summed over all $n$ steps, fib2’s true bit complexity is $\sum_{i=1}^n \mathcal{O}(i) = \mathcal{O}(n^2)$ — not $\mathcal{O}(n)$. The $\mathcal{O}(n)$ figure quoted above counts additions, which is the more common exam framing, but don’t read it as a bound on total bit operations.

3. Efficiency of Algorithms: Asymptotic Analysis

3.1 Why Not Just Count Clock Cycles?

Timing an algorithm on a specific machine is not useful for comparing algorithms:

  • Different machines have different speeds
  • Compilers optimise differently
  • Small input sizes hide the true growth pattern

We need a machine-independent measure of efficiency. Asymptotic analysis provides this by describing how the running time scales with input size as the input grows large.

3.2 Big-O Notation

Definition: We say $f(n) = \mathcal{O}(g(n))$ if there exist positive constants $c$ and $n_0$ such that:

\[f(n) \leq c \cdot g(n) \quad \text{for all } n \geq n_0\]

Read as: “$f(n)$ is Big-O of $g(n)$” or “$f$ is asymptotically at most $g$.”

Intuition: $\mathcal{O}(g(n))$ is an upper bound on the growth rate of $f(n)$, ignoring constant factors.

Examples:

  • $5n + 3 = \mathcal{O}(n)$ — take $c = 6$, $n_0 = 3$
  • $n^2 + 100n = \mathcal{O}(n^2)$ — take $c = 101$, $n_0 = 1$
  • $2^n + n^{100} = \mathcal{O}(2^n)$ — the exponential dominates
  • $\log n = \mathcal{O}(n)$ — logarithm grows slower than linear

Definition: $f(n) = \Omega(g(n))$ if $g(n) = \mathcal{O}(f(n))$ — lower bound.

Definition: $f(n) = \Theta(g(n))$ if $f(n) = \mathcal{O}(g(n))$ and $f(n) = \Omega(g(n))$ — tight bound.

3.3 Common Growth Classes

From slowest to fastest:

Class Name Example
$\mathcal{O}(1)$ Constant Array lookup
$\mathcal{O}(\log n)$ Logarithmic Binary search
$\mathcal{O}(n)$ Linear Finding maximum in array
$\mathcal{O}(n \log n)$ Log-linear Merge sort
$\mathcal{O}(n^2)$ Quadratic Bubble sort
$\mathcal{O}(n^3)$ Cubic Matrix multiplication (naive)
$\mathcal{O}(2^n)$ Exponential Naive Fibonacci
$\mathcal{O}(n!)$ Factorial Brute-force TSP

Practical implication: An algorithm that is polynomial in $n$ ($\mathcal{O}(n^k)$ for some constant $k$) is considered efficient. An exponential algorithm ($\mathcal{O}(c^n)$ for $c > 1$) is considered inefficient — it becomes unusable even for moderate input sizes.

3.4 Rules for Computing Big-O

  1. Drop constants: $\mathcal{O}(5n) = \mathcal{O}(n)$
  2. Drop lower-order terms: $\mathcal{O}(n^2 + n) = \mathcal{O}(n^2)$
  3. Ignore base of logarithm: $\mathcal{O}(\log_2 n) = \mathcal{O}(\log_{10} n) = \mathcal{O}(\log n)$ (since log base changes are just constant factors)
  4. Addition rule: if A runs in $\mathcal{O}(f(n))$ and B runs in $\mathcal{O}(g(n))$, A followed by B runs in $\mathcal{O}(f(n) + g(n)) = \mathcal{O}(\max(f(n), g(n)))$
  5. Multiplication rule: A nested loop where the outer runs $n$ times and the inner runs $n$ times is $\mathcal{O}(n^2)$

Per the textbook (Dasgupta et al.). The book itself states exactly four rules, each with its own canonical example:

  1. Drop multiplicative constants: $14n^2$ becomes $n^2$.
  2. $n^a$ dominates $n^b$ if $a > b$: $n^2$ dominates $n$.
  3. Any exponential dominates any polynomial: “$3^n$ dominates $n^5$ (it even dominates $2^n$).”
  4. Any polynomial dominates any logarithm: “$n$ dominates $(\log n)^3$” — which also means $n^2$ dominates $n \log n$.

The book also gives its own canonical “which running time is better?” example: $f_1(n) = n^2$ versus $f_2(n) = 2n + 20$. For $n \leq 5$, $f_1$ is smaller; thereafter $f_2$ wins, and keeps winning by an ever-widening margin, so $f_2 = \mathcal{O}(f_1)$ but $f_1 \neq \mathcal{O}(f_2)$. A third algorithm $f_3(n) = n+1$ is better than $f_2$, but only by a constant factor ($f_2 = \mathcal{O}(f_3)$ and $f_3 = \mathcal{O}(f_2)$, so Big-O treats them as equivalent) — a tiny difference compared to the $f_1$-versus-$f_2$ gap. This is exactly why Big-O ignores constant factors.

3.5 Worked Examples

Example 1: What is the Big-O complexity of this code?

for i = 1 to n:
    for j = 1 to n:
        print(i + j)

The outer loop runs $n$ times, inner loop runs $n$ times each → $\mathcal{O}(n^2)$.

Example 2: What about this?

for i = 1 to n:
    for j = i to n:
        print(i + j)

The inner loop runs $n - i + 1$ times. Total $= n + (n-1) + \dots + 1 = n(n+1)/2 = \mathcal{O}(n^2)$.

Example 3: Which is better for large $n$: an algorithm with running time $1000n$ or one with $n^2$?

  • At $n = 1000$: $1000n = 10^6$, $n^2 = 10^6$ (equal)
  • At $n = 2000$: $1000n = 2 \times 10^6$, $n^2 = 4 \times 10^6$ (the $\mathcal{O}(n)$ algorithm wins)
  • At $n = 10{,}000$: $1000n = 10^7$, $n^2 = 10^8$ (the $\mathcal{O}(n)$ algorithm is 10× faster)

Constant factors matter for small $n$, but asymptotic class dominates for large $n$.

4. Algorithms with Numbers

4.1 Representing Numbers

A number $N$ written in binary uses $\lceil \log_2(N+1) \rceil$ bits. We say the size of $N$ (as an input to an algorithm) is its number of bits, denoted $n = \lfloor \log_2 N \rfloor + 1$.

Important: When we say “an $\mathcal{O}(n)$ algorithm for numbers,” $n$ refers to the number of digits (bits), not the magnitude of the number. This distinction matters:

  • An algorithm that runs in $\mathcal{O}(N)$ time is exponential in $n$ (since $N = 2^n$ approximately)
  • An algorithm that runs in $\mathcal{O}(n)$ time is linear in the number of bits = polynomial

Per the textbook: Bases and Logs. Why is it always safe to write $\mathcal{O}(\log N)$ without saying which base? Because changing base only rescales $\log N$ by a constant factor: $\log_b N = (\log_a N)/(\log_a b)$, and Big-O absorbs constant factors. The function $\log N$ (base 2, unless stated otherwise) also has several equivalent everyday meanings:

  1. The power to which you must raise 2 to obtain $N$.
  2. The number of times you must halve $N$ to get down to 1 — useful whenever an algorithm halves its input at each step.
  3. The number of bits in the binary representation of $N$.
  4. The depth of a complete binary tree with $N$ nodes.
  5. Even, to within a constant factor, the harmonic sum $1 + \tfrac{1}{2} + \tfrac{1}{3} + \cdots + \tfrac{1}{N}$.

4.2 Addition Algorithm

To add two n-bit numbers:

  • Proceed bit by bit from least significant to most significant
  • Maintain a carry bit
Algorithm: Add(x, y)   [x, y are n-bit numbers]
  carry = 0
  for i = 0 to n-1:
      sum_bit = x[i] + y[i] + carry
      result[i] = sum_bit mod 2
      carry = sum_bit div 2
  result[n] = carry
  return result

Time complexity: $\mathcal{O}(n)$ — exactly $n$ additions of single bits.

4.3 Multiplication Algorithm

Grade-school multiplication of two n-digit numbers:

  • Multiply the first number by each digit of the second
  • Shift appropriately and add
Algorithm: Multiply(x, y)   [x, y are n-bit numbers]
  result = 0
  for i = 0 to n-1:
      if y[i] = 1:
          result = result + (x shifted left by i positions)
  return result

Time complexity:

  • Each row is an $n$-bit number (shifted), so at most $2n$ bits
  • We have $n$ rows to add
  • Each addition takes $\mathcal{O}(n)$ time
  • Total: $\mathcal{O}(n)$ additions × $\mathcal{O}(n)$ per addition = $\mathcal{O}(n^2)$

Note: Much faster algorithms exist (Karatsuba — covered in Module II), but $\mathcal{O}(n^2)$ is the grade-school baseline.

Per the textbook: a recursive view of multiplication. DPV also gives multiplication recursively, by peeling off one bit of $y$ at a time — this is the form that leads directly to Karatsuba in Module II:

\[x \cdot y = \begin{cases} 2 \cdot (x \cdot \lfloor y/2 \rfloor) & y \text{ even} \\ x + 2 \cdot (x \cdot \lfloor y/2 \rfloor) & y \text{ odd} \end{cases}\]

Each recursive call halves $y$ ($\mathcal{O}(n)$ levels), and each level does one $\mathcal{O}(n)$-time addition and shift — the same $\mathcal{O}(n^2)$ total as the grade-school method above, just derived recursively rather than tabulated row by row.

4.4 Division Algorithm

DPV also gives a recursive algorithm for division: given $x \geq 0$ and $y > 0$, compute $q, r$ with $x = qy + r$ and $0 \leq r < y$.

Algorithm: Divide(x, y)   [x, y are n-bit integers, y > 0]
  if x = 0: return (q, r) = (0, 0)
  (q, r) = Divide(⌊x/2⌋, y)     # recurse on x halved
  q = 2q, r = 2r                # undo the halving
  if x is odd: r = r + 1
  if r ≥ y: r = r - y, q = q + 1   # one correction step
  return (q, r)

The recursion computes $\lfloor x/2 \rfloor \div y$ first, then “undoes” the halving by doubling $q$ and $r$ and folding back in $x$’s last bit — doubling can push $r$ just past $y$, so a single correction step (subtract $y$ once, add 1 to $q$) restores $0 \leq r < y$.

Time complexity: $\mathcal{O}(n)$ recursive levels (one per bit of $x$), each doing $\mathcal{O}(n)$ work → $\mathcal{O}(n^2)$, the same as multiplication.

Check: Divide(13, 4) unwinds as $(0,0) \to (0,1) \to (0,3) \to (1,2) \to (3,1)$, matching $13 = 3\times4+1$.

5. Modular Arithmetic

5.1 Definitions

For integers $x$ and $N$ ($N > 0$), the expression $x \bmod N$ (also written $x \% N$) is the remainder when $x$ is divided by $N$. It satisfies:

\[x = qN + r \quad \text{where } q = \lfloor x/N \rfloor \text{ and } r = x \bmod N, \; 0 \leq r < N\]

We say $x \equiv y \pmod{N}$ (“$x$ is congruent to $y$ modulo $N$”) if $N$ divides $(x - y)$, i.e., $x \bmod N = y \bmod N$.

Examples:

  • $17 \bmod 5 = 2$ (since $17 = 3 \times 5 + 2$)
  • $23 \equiv 8 \pmod{5}$ (since $23 - 8 = 15 = 3 \times 5$)
  • $-3 \bmod 5 = 2$ (since $-3 = (-1) \times 5 + 2$)

5.2 Properties of Modular Arithmetic

Modular arithmetic satisfies the usual algebraic properties:

\[\begin{aligned} (x + y) \bmod N &= ((x \bmod N) + (y \bmod N)) \bmod N \\ (x \times y) \bmod N &= ((x \bmod N) \times (y \bmod N)) \bmod N \\ (x^y) \bmod N &= ((x \bmod N)^y) \bmod N \end{aligned}\]

These properties mean we can reduce numbers modulo $N$ at each step of a computation, keeping numbers small.

5.3 Modular Exponentiation

Problem: Compute $x^y \bmod N$, where $x, y, N$ can be very large (hundreds of digits).

Naive approach: Multiply $x$ by itself $y$ times, reducing mod $N$ at each step. This takes $\mathcal{O}(y)$ multiplications — but $y$ can be exponentially large, so this is too slow.

Fast approach — Repeated Squaring:

Key idea: use the binary representation of $y$.

  • If $y$ is even: $x^y = (x^{y/2})^2$
  • If $y$ is odd: $x^y = x \cdot x^{y-1}$
Algorithm: ModExp(x, y, N)
  if y = 0: return 1
  z = ModExp(x, ⌊y/2⌋, N)
  if y is even: return z² mod N
  else:         return x · z² mod N

Time complexity: $y$ is halved at each step → $\mathcal{O}(\log y)$ multiplications. Each multiplication involves numbers of size at most $2 \log_2 N$ bits, taking $\mathcal{O}(\log^2 N)$ time. Total: $\mathcal{O}(\log y \cdot \log^2 N)$ — very efficient even for hundred-digit numbers.

Worked Example: Compute $3^{13} \bmod 7$.

Binary of 13 = 1101. Build up powers of 3:

  • $3^1 \bmod 7 = 3$
  • $3^2 \bmod 7 = 9 \bmod 7 = 2$
  • $3^4 \bmod 7 = (3^2)^2 \bmod 7 = 4 \bmod 7 = 4$
  • $3^8 \bmod 7 = (3^4)^2 \bmod 7 = 16 \bmod 7 = 2$

Now $3^{13} = 3^8 \cdot 3^4 \cdot 3^1 \bmod 7 = 2 \cdot 4 \cdot 3 \bmod 7 = 24 \bmod 7 = 3$.

6. Euclid’s Algorithm for GCD

6.1 The Problem

The greatest common divisor $\gcd(a, b)$ is the largest integer that divides both $a$ and $b$.

Examples:

  • $\gcd(12, 8) = 4$
  • $\gcd(100, 75) = 25$
  • $\gcd(7, 13) = 1$ (since both are prime and different)
  • $\gcd(a, 0) = a$ for any $a \geq 0$

6.2 The Key Property

Lemma: $\gcd(a, b) = \gcd(b, a \bmod b)$

Proof sketch: Any common divisor of $a$ and $b$ also divides $a - b$ (and hence $a - qb = a \bmod b$). Conversely, any common divisor of $b$ and $(a \bmod b)$ also divides $a = q \cdot b + (a \bmod b)$. So the set of common divisors is the same, and hence the gcd is the same. □

This gives us the algorithm:

Algorithm: Euclid(a, b)
  if b = 0: return a
  return Euclid(b, a mod b)

6.3 Worked Example

$\gcd(1071, 462)$: \(\begin{aligned} \gcd(1071, 462) &= \gcd(462, 147) && [1071 = 2 \times 462 + 147] \\ &= \gcd(147, 21) && [462 = 3 \times 147 + 21] \\ &= \gcd(21, 0) && [147 = 7 \times 21 + 0] \\ &= 21 \end{aligned}\)

6.4 Time Complexity

Lamé’s Theorem: The number of steps in Euclid’s algorithm is at most 5 times the number of decimal digits of the smaller input.

More precisely, if $a > b$, the algorithm takes at most $\mathcal{O}(\log(\min(a,b)))$ steps. Each step involves one division (mod operation), which takes $\mathcal{O}(n^2)$ time for $n$-bit numbers.

Total time: $\mathcal{O}(n^3)$ where $n$ is the number of bits. In practice, it is much faster than this worst-case bound.

6.5 Extended Euclidean Algorithm

The extended version computes integers $x, y$ such that:

\[ax + by = \gcd(a, b)\] 
Algorithm: ExtendedEuclid(a, b)
  if b = 0: return (a, 1, 0)   [gcd, x, y]
  (d, x', y') = ExtendedEuclid(b, a mod b)
  return (d, y', x' - ⌊a/b⌋ · y')

This is important for modular inverses: if $\gcd(a, N) = 1$, then $x$ is the multiplicative inverse of $a$ modulo $N$ (i.e., $ax \equiv 1 \bmod N$).

7. Primality Testing

7.1 What Is a Prime?

A positive integer $p > 1$ is prime if it has no divisors other than 1 and itself. Otherwise it is composite.

Examples of primes: 2, 3, 5, 7, 11, 13, 17, 19, 23, …

Why do we care? Primality testing is central to public-key cryptography (RSA). As the textbook itself puts it: “Factoring is hard. Primality is easy.” This strange disparity between two intimately related problems — one very hard, one very easy — lies at the heart of the technology that enables secure communication across the internet today.

7.2 Trial Division

The simplest method: check whether any integer from 2 to $\sqrt{N}$ divides $N$.

Algorithm: IsPrime(N)
  if N = 2: return true
  if N is even: return false
  for d = 3, 5, 7, ... while d² ≤ N:
      if d divides N: return false
  return true

Time complexity: $\mathcal{O}(\sqrt{N})$ divisions $= \mathcal{O}(2^{n/2})$ = exponential in $n$ (where $n$ = number of bits of $N$).

For a 100-digit number $N$ ($n \approx 332$ bits), $\sqrt{N} \approx 10^{50}$ — impossibly slow.

7.3 Fermat’s Little Theorem

Theorem (Fermat): If $p$ is prime and $0 < a < p$, then:

\[a^{p-1} \equiv 1 \pmod{p}\]

Proof idea: The set $\{a, 2a, 3a, \dots, (p-1)a\}$ modulo $p$ is a permutation of $\{1, 2, \dots, p-1\}$. Multiplying both sides together: $a^{p-1} \cdot (p-1)! \equiv (p-1)! \pmod{p}$. Since $\gcd((p-1)!, p) = 1$, we can cancel to get $a^{p-1} \equiv 1 \pmod{p}$. □

Using FLT for primality: To test if $N$ is prime, pick a random $a$ and check whether $a^{N-1} \equiv 1 \pmod{N}$.

  • If the congruence fails: N is definitely composite.
  • If the congruence holds: N is probably prime (but might be composite).
Algorithm: Primality(N, k)
  for i = 1 to k:
      pick a at random from {1, ..., N-1}
      if a^(N-1) mod N ≠ 1: return composite
  return prime (probably)

Time complexity: Each trial uses one modular exponentiation, $\mathcal{O}(\log^2 N)$; total over $k$ trials: $\mathcal{O}(k \log^2 N)$.

Caveat — Carmichael numbers: There exist composite numbers (e.g., $561 = 3 \times 11 \times 17$) that pass the Fermat test for every $a$ with $\gcd(a, N) = 1$. These are called Carmichael numbers. They are rare but do exist.

7.4 Miller-Rabin Primality Test

The Miller-Rabin test strengthens the Fermat test to catch Carmichael numbers. The idea is based on the fact that for a prime $p$, the only square roots of 1 modulo $p$ are $\pm 1$ — so a nontrivial square root of 1 (some $x \not\equiv \pm1 \pmod N$ with $x^2 \equiv 1 \pmod N$) is a certificate that $N$ is composite, even if $N$ passes the ordinary Fermat test.

Since $N$ is odd, write $N - 1 = 2^t u$ with $u$ odd (pulling out every factor of 2). Instead of computing $a^{N-1} \bmod N$ blindly, watch the whole squaring chain \(a^u \bmod N,\ a^{2u} \bmod N,\ a^{4u} \bmod N,\ \ldots,\ a^{2^t u} \bmod N = a^{N-1} \bmod N,\) and check whether a nontrivial square root of 1 appears anywhere in it before flagging “probably prime.”

Do not confuse the two error bounds in this section. Plain repeated Fermat testing (§7.3) only guarantees error $\leq (1/2)^k = 2^{-k}$ on non-Carmichael composites, and can fail completely on a Carmichael number no matter how large $k$ is. Miller-Rabin’s square-root check gives the strictly stronger bound

\[\Pr(\text{Miller-Rabin reports "prime" on a composite } N) \leq \left(\frac{1}{4}\right)^k = 2^{-2k}\]

on every composite, Carmichael numbers included — because at least three-fourths of the bases $a \in \{1, \ldots, N-1\}$ reveal compositeness for any composite $N$. This is exactly why Miller-Rabin, not repeated Fermat, is the primality test used in practice.

In practice (with $k = 50$ repetitions, giving error at most $2^{-100}$), the test is used to reliably generate large primes for cryptography.

Time complexity: $\mathcal{O}(k \log^2 N)$ — polynomial in $n$, and in practice very fast.

8. Summary

Topic Key Result
Fibonacci — naive $\mathcal{O}(\varphi^n)$ exponential time
Fibonacci — iterative $\mathcal{O}(n)$ polynomial time
Big-O $f = \mathcal{O}(g)$ means $f$ grows no faster than $g$ (up to constants)
Addition of $n$-bit numbers $\mathcal{O}(n)$
Multiplication of $n$-bit numbers $\mathcal{O}(n^2)$ (grade school)
Modular exponentiation $\mathcal{O}(\log y \cdot \log^2 N)$
Euclid’s GCD $\mathcal{O}(n^3)$ in worst case, $\mathcal{O}(n)$ steps
Primality — trial division $\mathcal{O}(2^{n/2})$ — exponential
Primality — Fermat test $\mathcal{O}(\log^2 N)$ — polynomial

Central theme of this module: The difference between exponential and polynomial algorithms is the difference between impractical and practical. Clever algorithmic thinking — not just translating definitions to code — is what makes algorithms efficient.

9. Practice Problems

  1. Compute fib(8) using the iterative algorithm, showing each step. How many additions are performed?

  2. Write memoFib (memoised Fibonacci — see §2.2, not to be confused with the book’s own fib2) in Python. Time it for n = 30 vs fib1.

  3. Determine the Big-O complexity of each:
    • a) $T(n) = 7n^2 + 3n + 100$
    • b) $T(n) = 5 \log n + 2n$
    • c) $T(n) = n \cdot \log n + n^2$

  4. True or False: $\mathcal{O}(2n) = \mathcal{O}(n)$. Justify.

  5. Show that if $f(n) = \mathcal{O}(g(n))$ and $g(n) = \mathcal{O}(h(n))$, then $f(n) = \mathcal{O}(h(n))$.

  6. Compute $\gcd(840, 252)$ using Euclid’s algorithm. Show all steps.

  7. Use the extended Euclidean algorithm to find $x, y$ such that $17x + 13y = \gcd(17, 13)$.

  8. Compute $7^{100} \bmod 11$ using fast modular exponentiation.

  9. Use Fermat’s Little Theorem to show $3^{10} \equiv 1 \pmod{11}$.

  10. Is 91 prime? Test using trial division. Show your work.

  11. Show that the Fermat test with base $a = 2$ does not detect the Carmichael number $341 = 11 \times 31$ (i.e., verify that $2^{340} \equiv 1 \pmod{341}$).

  12. Challenge: Prove that the grade-school multiplication algorithm runs in $\mathcal{O}(n^2)$, where $n$ is the number of bits.
Course Home Next Module →