Module I — Introduction to 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.

2. Computing Fibonacci Numbers

The Fibonacci sequence is defined as:

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 Algorithm 2 — Memoisation (Polynomial Time)

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

function fib2(n):
    create array T[0..n], initialise all to -1
    T[0] = 0
    T[1] = 1
    return helper(n, T)

function helper(n, T):
    if T[n] ≠ -1: return T[n]
    T[n] = helper(n-1, T) + helper(n-2, T)
    return T[n]

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

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

2.3 Algorithm 3 — Iterative (Polynomial Time, Better)

Even simpler: compute from the bottom up.

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

Time complexity: $O(n)$ time, $O(1)$ space (only three variables needed).

2.4 Comparison

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.

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 $O(1)$ for very large $n$. But for our purposes, we count the number of addition 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) = O(g(n))$ if there exist positive constants $c$ and $n_0$ such that:

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

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

Examples:

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

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

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

3.3 Common Growth Classes

From slowest to fastest:

Practical implication: An algorithm that is polynomial in $n$ ($O(n^k)$ for some constant $k$) is considered efficient. An exponential algorithm ($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: $O(5n) = O(n)$
2. Drop lower-order terms: $O(n^2 + n) = O(n^2)$
3. Ignore base of logarithm: $O(\log_2 n) = O(\log_{10} n) = O(\log n)$ (since log base changes are just constant factors)
4. Addition rule: if A runs in $O(f(n))$ and B runs in $O(g(n))$, A followed by B runs in $O(f(n) + g(n)) = 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 $O(n^2)$

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 → $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 = 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 $O(n)$ algorithm wins)
• At $n = 10{,}000$: $1000n = 10^7$, $n^2 = 10^8$ (the $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 $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 $O(N)$ time is exponential in $n$ (since $N = 2^n$ approximately)
• An algorithm that runs in $O(n)$ time is linear in the number of bits = polynomial

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: $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 $O(n)$ time
• Total: $O(n)$ additions × $O(n)$ per addition = $O(n^2)$

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

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:

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:

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 $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 → $O(\log y)$ multiplications. Each multiplication involves numbers of size at most $2 \log_2 N$ bits, taking $O(\log^2 N)$ time. Total: $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)   [a ≥ b ≥ 0]
  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 $O(\log(\min(a,b)))$ steps. Each step involves one division (mod operation), which takes $O(n^2)$ time for $n$-bit numbers.

Total time: $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:

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). Modern secure communication depends on the fact that factoring large numbers is hard, while testing primality is easy.

7.2 Trial Division

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

Algorithm: isPrime_trial(N)
  for d = 2 to √N:
      if d divides N: return False
  return True

Time complexity: $O(\sqrt{N})$ divisions $= 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:

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: Fermat_test(N)
  pick random a with 1 < a < N
  if a^(N-1) mod N ≠ 1: return COMPOSITE
  return PROBABLY PRIME

Time complexity: $O(\log^2 N)$ — just one modular exponentiation.

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 (Conceptual)

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$.

The test is randomised: if $N$ is composite, it returns COMPOSITE with probability $\geq 1/2$ for a randomly chosen $a$. Repeating $k$ times gives error probability $\leq 2^{-k}$.

In practice (with $k = 50$ repetitions), the test is used to reliably generate large primes for cryptography.

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

8. Summary

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 fib2 (memoised Fibonacci) 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: $O(2n) = O(n)$. Justify.

5. Show that if $f(n) = O(g(n))$ and $g(n) = O(h(n))$, then $f(n) = 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 $O(n^2)$, where $n$ is the number of bits.