Intro to Algorithms

An algorithm is a finite, unambiguous sequence of instructions that solves a problem. Given some input, it follows a fixed procedure and eventually produces an output.

The definition has two parts worth paying attention to. First: finite. An algorithm must always terminate. A procedure that runs forever is not an algorithm. Second: unambiguous. Every step must be completely clear — there is no room for interpretation, no "use your judgment here." The instructions are mechanical. This is what makes them executable, even by a machine with no understanding whatsoever of the problem being solved.

What Does an Algorithm Need?

Three things:

1. Input — one or more values given to the algorithm (possibly nothing, in the case of algorithms that generate fixed outputs).
2. A finite sequence of instructions — the procedure itself.
3. Output — one or more values produced as a result.

The problem statement defines the relationship between input and output. It specifies what the input space looks like (what kinds of values are valid) and what the output should be for each possible input. There are infinitely many sequences of instructions that could satisfy the same problem statement — that is, infinitely many algorithms that compute the same function. They may differ in speed, in memory usage, in elegance, or in nothing at all. Part of what we study is how to compare them and choose the best one.

A Quick Example: Euclid's Algorithm

The greatest common divisor (GCD) of two integers $x$ and $y$ is the largest integer that divides both without a remainder. The question is: given $x$ and $y$, how do you compute it?

Euclid figured this out around 300 BC. His insight: if you divide $x$ by $y$ and get remainder $r$, then $\gcd(x, y) = \gcd(y, r)$. The GCD of the original pair equals the GCD of the divisor and the remainder. Keep applying this until the remainder is zero — at that point, the last non-zero divisor is the answer.

In pseudocode:

function GCD(x, y):
    if y == 0:
        return x
    else:
        r = x mod y
        return GCD(y, r)

This is a recursive algorithm — it calls itself with smaller inputs. Each call reduces the problem: $y$ gets smaller, and eventually it reaches zero. At that point the recursion bottoms out and the answer is returned.

Notice that this is also the abstract nature of a good algorithm: the idea is simple enough to state in a few lines, it terminates provably, and it gives the correct answer. You do not need to understand number theory to implement it — you just follow the steps.

---

The Core Questions in Algorithm Design

Before we dive into specific algorithms, it is worth knowing what questions we are always trying to answer. They fall into three categories.

Understanding the problem. What are the valid inputs? What must the output look like? Are there mathematical properties of the problem we can exploit? Most algorithmic breakthroughs come not from clever code but from a deeper insight about the mathematical structure of the problem. Euclid's algorithm works because of a number-theoretic property of GCD, not because of a programming trick.

Measuring efficiency. How fast does the algorithm run? How much memory does it need? These are the two resources we care about. We want algorithms that are both fast and frugal with memory — and when there is a tension between the two, we want to understand the tradeoff explicitly.

Learning patterns. Most new problems are not entirely new. They share structure with problems that have already been solved. If you know your classical algorithms and data structures, you can often solve a new problem by recognising which pattern it belongs to and adapting a known solution. This is why we study a catalogue of techniques — not to memorise them, but to have them available as building blocks.

---

The Fibonacci Case Study

Now we get to the real work. The lecture uses Fibonacci numbers as a running example, and it is the perfect choice. The problem is simple enough that you can explain it in one sentence, but the journey from the worst solution to the best solution involves every major concept in algorithmic analysis. Pay attention.

What Are Fibonacci Numbers?

The Fibonacci sequence is:

$1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, \ldots$

Each number is the sum of the two that precede it. Formally, the sequence is defined by the recurrence relation:

$F_n = \begin{cases} 1 & \text{if } n = 1 \text{ or } n = 2 \\ F_{n-1} + F_{n-2} & \text{if } n > 2 \end{cases}$

(By convention, $F_0 = 0$ is sometimes used, but the course uses $F_1 = F_2 = 1$.)

The problem: given $n$, compute $F_n$.

This sounds trivial. It is not. There are at least six meaningfully different algorithms for computing $F_n$, ranging from a closed formula to a logarithmic-time matrix method — and understanding why each one is better or worse than the previous one is the whole point.

---

Algorithm 1: The Closed Formula

There is an exact formula for $F_n$, derived from the theory of linear recurrences:

$F_n = \frac{1}{\sqrt{5}} \left( \varphi^n - \hat{\varphi}^n \right)$

where $\varphi = \frac{1 + \sqrt{5}}{2} \approx 1.618$ (the golden ratio) and $\hat{\varphi} = \frac{1 - \sqrt{5}}{2} \approx -0.618$.

In pseudocode:

function Fib1(n):
    return round( (1/√5) * (φⁿ - φ̂ⁿ) )

Time: $O(1)$ — constant. The computation does not depend on $n$ in terms of number of steps.

Space: $O(1)$ — constant. Just a few variables.

Sounds perfect. Sadly, it does not work.

The problem is numerical precision. Both $\varphi$ and $\hat{\varphi}$ are irrational numbers. They cannot be represented exactly in any floating-point format. Every computation with them introduces a tiny rounding error. For small $n$ this error rounds correctly — $\text{Fib1}(3)$ gives $1.999863 \approx 2$, which rounds to the right answer. But for $n = 18$, $\text{Fib1}(18)$ gives $2583.023$, which rounds to $2583$ — but the correct answer is $F_{18} = 2584$. Off by one.

You might think: use higher precision arithmetic. But the errors grow with $n$, and no fixed-precision representation can keep up indefinitely. The formula is mathematically exact but computationally useless for large $n$. We need a different approach.

---

Algorithm 2: Naive Recursion

The recurrence definition of Fibonacci translates directly into a recursive algorithm:

function Fib2(n):
    if n ≤ 2:
        return 1
    else:
        return Fib2(n-1) + Fib2(n-2)

This is the most natural algorithm anyone would write. Follow the definition. If the base case, return 1. Otherwise, recurse on both predecessors and add.

Does it work? Yes, it produces the correct answer. Is it any good? No. It is catastrophically slow.

The Recursion Tree

To understand why, draw out what happens when you call $\text{Fib2}(5)$:

• $\text{Fib2}(5)$ calls $\text{Fib2}(4)$ and $\text{Fib2}(3)$
• $\text{Fib2}(4)$ calls $\text{Fib2}(3)$ and $\text{Fib2}(2)$
• $\text{Fib2}(3)$ calls $\text{Fib2}(2)$ and $\text{Fib2}(1)$

Notice that $\text{Fib2}(3)$ is computed twice — once as a child of $\text{Fib2}(5)$, once as a child of $\text{Fib2}(4)$. And $\text{Fib2}(2)$ is computed three times. The recursion tree grows explosively because sub-problems are solved repeatedly without any memory of previous results.

This is the fundamental flaw. The algorithm forgets everything it has computed the moment a call returns.

Measuring Memory Usage

Each recursive call occupies memory. When a function calls itself, the current call is not finished — it is suspended, waiting for the recursive call to return. The suspended call must be stored somewhere. That storage is the call stack, and each suspended call occupies an activation record containing the local variables and the return address.

The memory usage of Fib2 at any moment equals the depth of the deepest active chain of calls — the longest root-to-leaf path in the recursion tree. For $\text{Fib2}(n)$, this path has length $n$ (one call per level, decreasing $n$ by 1 each time down the leftmost branch). So memory usage is $O(n)$.

Measuring Running Time — The Right Way

Here is an important methodological point. We do not measure running time in seconds. A second is machine-dependent, compiler-dependent, operating-system-dependent, and even mood-of-the-hardware-dependent. Instead, we count elementary operations — basic computational steps that each take a fixed, constant amount of time regardless of input. Things like: one addition, one comparison, one assignment, one function return.

The total running time is then proportional to the total number of elementary operations. This count is machine-independent.

For Fib2, define $T(n)$ as the number of nodes in the recursion tree — which is proportional to the total number of elementary operations, since each call does at most a constant amount of work (one comparison, possibly one addition, one return).

$T(n)$ satisfies the recurrence:

$T(n) = \begin{cases} 1 & n \leq 2 \\ T(n-1) + T(n-2) + 1 & n > 2 \end{cases}$

The extra $+1$ counts the root node itself. Now we want to bound this.

Lower Bound for $T(n)$

We want to show $T(n)$ grows at least exponentially. The key step: since the recursion tree for $\text{Fib2}(n-1)$ is at least as large as for $\text{Fib2}(n-2)$ (larger input = more nodes), we have $T(n-1) \geq T(n-2)$. So:

$T(n) = T(n-1) + T(n-2) + 1 \geq 2T(n-2) + 1$

Now unroll this inequality repeatedly:

$T(n) \geq 2T(n-2) + 1 \geq 4T(n-4) + 2 + 1 \geq 8T(n-6) + 4 + 2 + 1 \geq \cdots$

At the $k$-th step:

$T(n) \geq 2^k \cdot T(n - 2k) + \sum_{i=0}^{k-1} 2^i$

We stop when $n - 2k \leq 2$, which means $k \geq \lfloor n/2 \rfloor$. At that point $T(n-2k) \geq 1$, and the geometric sum $\sum_{i=0}^{k-1} 2^i = 2^k - 1$. So:

$T(n) \geq 2^{\lfloor n/2 \rfloor} + 2^{\lfloor n/2 \rfloor} - 1 \geq 2^{\lfloor n/2 \rfloor}$

Conclusion: $T(n) = \Omega(2^{n/2})$. The running time grows at least as fast as $2^{n/2}$.

Upper Bound for $T(n)$

For the upper bound, use the reverse inequality: $T(n-2) \leq T(n-1)$, so:

$T(n) = T(n-1) + T(n-2) + 1 \leq 2T(n-1) + 1$

Unrolling similarly:

$T(n) \leq 2T(n-1) + 1 \leq 4T(n-2) + 3 \leq 8T(n-3) + 7 \leq \cdots$

At the $k$-th step:

$T(n) \leq 2^k T(n-k) + \sum_{i=0}^{k-1} 2^i$

Stop when $n - k \leq 2$, i.e. $k = n - 2$. Then:

$T(n) \leq 2^{n-2} \cdot T(2) + 2^{n-2} - 1 = 2^{n-2} + 2^{n-2} - 1 = 2 \cdot 2^{n-2} - 1 \leq 2^n$

Conclusion: $T(n) = O(2^n)$. Together with the lower bound: the running time of Fib2 is exponential in $n$.

What does exponential mean in practice? For $n = 50$, you are computing roughly $2^{25} \approx 33$ million operations. For $n = 100$, it is around $2^{50} \approx 10^{15}$ operations. On a modern CPU doing $10^9$ operations per second, $n = 100$ would take over a million seconds — about two weeks. Fib2 is completely unusable for any meaningful $n$.

[!WARNING] Exponential time algorithms are not just "slow" — they are practically useless. The difference between an $O(n)$ and an $O(2^n)$ algorithm is not a matter of degree; it is a categorical difference in what is computable in practice.

The root cause of Fib2's failure: repeated computation. Every sub-problem is solved from scratch, as if it had never been solved before. The fix is obvious in hindsight — remember what you have computed.

---

Algorithm 3: Iterative Solution with Array

The insight: compute Fibonacci numbers bottom-up, starting from $F_1$ and $F_2$, and store every intermediate result so you never compute anything twice.

function Fib3(n):
    let F[1..n] be a new array
    F[1] = 1
    F[2] = 1
    for i = 3 to n:
        F[i] = F[i-1] + F[i-2]
    return F[n]

Time analysis. Count the operations:

• Array creation: 1 operation
• Two assignments (F[1], F[2]): 2 operations
• The loop runs $n - 2$ times, doing a sum and an assignment each time: $2(n-2)$ operations
• Return: 1 operation
• Total: $3n - 2$ operations for $n > 2$

Running time is $O(n)$ — linear. Dramatically better than exponential.

Space analysis. We store an array of $n$ integers, plus the loop variable $i$ and the input $n$. Total space: $O(n)$.

This is correct, fast, and simple. But can we do better on memory?

---

Algorithm 4: Memory-Efficient Iterative Solution

Look at the loop in Fib3 again. To compute $F[i]$, you only need $F[i-1]$ and $F[i-2]$. You never look at $F[i-3]$ or anything earlier. So why are you storing all $n$ values?

You do not need to. You only need the two most recent values:

function Fib4(n):
    a = 1
    b = 1
    for i = 3 to n:
        c = a + b
        a = b
        b = c
    return b

Here a and b always hold the two most recent Fibonacci numbers. Each iteration: compute their sum into c, then shift: a gets the old b, b gets the new c. After $n-2$ iterations, b holds $F_n$.

Time analysis. Count operations:

• Two assignments: 2 operations
• Loop runs $n-2$ times, doing a sum and three assignments: $4(n-2)$ operations
• Plus the loop counter: $n-2$ more
• Return: 1 operation
• Total: $5n - 7$ operations

Slightly more operations than Fib3 (the constant factor is larger: 5 vs 3). But the asymptotic class is the same: $O(n)$.

Space analysis. Five variables: $n$, $i$, $a$, $b$, $c$. That is $O(1)$ — constant space, regardless of $n$. We eliminated the $O(n)$ array entirely.

[!NOTE] This illustrates a crucial lesson: you can sometimes trade space for time and vice versa. Fib3 uses $O(n)$ space to compute each result exactly once. Fib4 uses $O(1)$ space by computing the same things in a different order, without storing intermediate results. The time complexity is the same; the space complexity is not.

---

Algorithm 5: Matrix Power Solution

Here is an elegant mathematical result that opens the door to a faster algorithm.

Theorem. Let $A = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}$. For every $n \geq 2$:

$A^{n-1} = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}^{n-1} = \begin{pmatrix} F_n & F_{n-1} \\ F_{n-1} & F_{n-2} \end{pmatrix}$

So $F_n$ appears in the top-left corner of $A^{n-1}$. If you can compute matrix powers, you can compute Fibonacci numbers.

Proof by mathematical induction. We need to introduce this proof technique carefully because you will use it constantly.

Mathematical induction is a method for proving that a property $P(n)$ holds for all natural numbers $n$ above some starting value. It works in two steps:

1. Base case: Show that $P$ is true for the starting value (here, $n = 2$).
2. Inductive step: Assume that $P$ is true for all values up to some $k$, then show it must be true for $k + 1$.

The intuition: if you can walk from the first step to any subsequent step, and you are already on the first step, you can reach any step.

Base case ($n = 2$): $A^1 = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix} = \begin{pmatrix} F_2 & F_1 \\ F_1 & F_0 \end{pmatrix}$ where $F_0 = 0$, $F_1 = 1$, $F_2 = 1$. ✓

Inductive step: Assume the theorem holds for $k$, i.e. $A^{k-1} = \begin{pmatrix} F_k & F_{k-1} \\ F_{k-1} & F_{k-2} \end{pmatrix}$. Then:

$A^k = A^{k-1} \cdot A = \begin{pmatrix} F_k & F_{k-1} \\ F_{k-1} & F_{k-2} \end{pmatrix} \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix} = \begin{pmatrix} F_k + F_{k-1} & F_k \\ F_{k-1} + F_{k-2} & F_{k-1} \end{pmatrix} = \begin{pmatrix} F_{k+1} & F_k \\ F_k & F_{k-1} \end{pmatrix}$

which is exactly the required form for $n = k+1$. ✓

The proof is complete.

A naive matrix-power algorithm just multiplies $A$ by itself $n-2$ times:

function Fib5(n):
    A = [[1,1],[1,0]]
    for i = 3 to n:
        A = A × [[1,1],[1,0]]
    return A[1][1]

Time: $O(n)$ — no better than Fib4. Space: $O(1)$ — three variables. No improvement yet. But the theorem sets up something much better.

---

Algorithm 6: Fast Matrix Power — The Key Insight

The whole point of the matrix formulation is that we can now use fast exponentiation.

The key observation: to compute $A^n$, you do not need to do $n-1$ multiplications. You can use the following:

$A^n = \begin{cases} (A^{n/2})^2 & \text{if } n \text{ is even} \\ A \cdot (A^{(n-1)/2})^2 & \text{if } n \text{ is odd} \end{cases}$

Why does this help? Because each step halves the exponent. To go from $A^{32}$ to $A^{64}$, you just square once, not multiply 32 more times. The total number of multiplications needed to reach $A^n$ is proportional to $\log_2 n$.

For example, to compute $A^{16}$:

• $A^1 \to A^2$ (square once)
• $A^2 \to A^4$ (square again)
• $A^4 \to A^8$ (square again)
• $A^8 \to A^{16}$ (square again)

Four multiplications, not fifteen.

The recursive algorithm:

function FibMatPow(n):
    A = [[1,1],[1,0]]
    if n > 1:
        M = FibMatPow(n/2)    ⊳ integer division
        A = M × M
        if n mod 2 ≠ 0:       ⊳ n is odd
            A = A × [[1,1],[1,0]]
    return A

function Fib6(n):
    M = FibMatPow(n-1)
    return M[1][1]

Time: $O(\log n)$. Each recursive call halves $n$, so there are at most $\log_2 n$ recursive calls. Each call does a constant number of matrix multiplications (each of which is $O(1)$ for $2 \times 2$ matrices).

Space: $O(\log n)$. There are $\log_2 n$ active recursive calls at most, each holding a constant-size activation record.

Going from $O(n)$ to $O(\log n)$ is enormous. For $n = 10^9$:

• Fib4/Fib5 need about $10^9$ operations
• Fib6 needs about $\log_2(10^9) \approx 30$ operations

That is the difference between tens of seconds and a microsecond.

[!MATH] Exponentiation by squaring is a general technique that applies to any associative operation, not just matrix multiplication. It works for modular exponentiation in cryptography, polynomial powers, and even string operations. Recognising the pattern is a skill: whenever you see "compute $X^n$" for some object $X$ and large $n$, exponentiation by squaring is almost always the right tool.

---

Comparing All Six Algorithms

Here is the full picture:

Algorithm	Method	Time	Space
Fib1	Closed formula	$O(1)$	$O(1)$
Fib2	Naive recursion	$\Omega(2^{n/2})$	$O(n)$
Fib3	Iterative + array	$O(n)$	$O(n)$
Fib4	Iterative, 2 vars	$O(n)$	$O(1)$
Fib5	Matrix, naive power	$O(n)$	$O(1)$
Fib6	Matrix, fast power	$O(\log n)$	$O(\log n)$

Fib1 looks best but is broken. Fib2 is correct but exponential — unusable. Fib3 and Fib4 are both $O(n)$, with Fib4 using less memory. Fib5 is $O(n)$ with matrices (no better than Fib4 on its own). Fib6 is the winner: $O(\log n)$ time, $O(\log n)$ space.

All six algorithms compute exactly the same mathematical function — the $n$-th Fibonacci number. Their correctness is not what distinguishes them. Their computational efficiency is everything.

---

Input Value vs Input Size

There is a subtle but important point that the lecture raises at the end, and it is worth understanding precisely.

Throughout the analysis above, we measured time and space in terms of $n$ — the input value, the actual number you pass to the function. But computer scientists prefer to measure complexity in terms of the input size — the number of bits needed to represent the input.

To represent the integer $n$ in binary, you need $\lceil \log_2 n \rceil$ bits. Call this $|n|$. Then:

$|n| \approx \log_2 n \qquad \Longrightarrow \qquad n \approx 2^{|n|}$

Now re-express all complexities in terms of $|n|$:

| Algorithm | Time (in $|n|$) | Space (in $|n|$) | |---|---|---| | Fib1 | $O(1)$ | $O(1)$ | | Fib2 | $\Omega(2^{2|n|})$ | $O(2^{|n|})$ | | Fib3 | $O(2^{|n|})$ | $O(2^{|n|})$ | | Fib4 | $O(2^{|n|})$ | $O(1)$ | | Fib5 | $O(2^{|n|})$ | $O(1)$ | | Fib6 | $O(|n|)$ | $O(|n|)$ |

This is a different table even though the actual running times are identical. What changed is the lens through which we evaluate them.

Fib4 is $O(n)$ in terms of input value, which sounds linear and efficient. But in terms of input size it is $O(2^{|n|})$ — exponential. This means: doubling the number of bits in the input squares the running time. That is not a polynomial algorithm in the proper theoretical sense.

Only Fib6 is genuinely efficient by this measure: $O(|n|)$ in input size. The algorithm's running time grows linearly with the number of bits used to represent the input. That is what it means to be a polynomial-time algorithm.

[!NOTE] This distinction — input value vs input size — becomes critical in complexity theory. An algorithm that runs in $O(n)$ where $n$ is a numerical input value might still be exponential in the formal sense. This is why problems like the Travelling Salesman Problem are hard: the input size is $O(V^2)$ (the graph), but naive algorithms run in $O(V!)$ which is super-exponential in the input size. We will return to this distinction when we study NP-completeness.

---

Summary

What this lecture establishes is not a set of facts to memorise — it is a way of thinking.

Every algorithm has a time cost and a space cost. Both are measured in terms of input size using asymptotic notation. The same function can be computed by algorithms that differ by an exponential factor in efficiency. The difference is not academic: it is the difference between an algorithm that runs in a microsecond and one that would outlast the universe.

The Fibonacci example compresses the entire arc of algorithm design into one problem: naive approach, recognise the flaw (repeated computation), fix it iteratively, reduce the memory footprint, find the mathematical structure (matrix representation), exploit the structure (fast exponentiation), and arrive at a logarithmic algorithm.

That arc — from naive to optimal — is the template for everything that follows in this course.