Unit 1: Foundations of Algorithm — Comprehensive Study Notes

1. Algorithms & Knuth's Formal Foundations

An Algorithm is an unambiguous, step-by-step computational procedure that takes a valid set of inputs and transforms them into a well-defined set of outputs within a finite amount of time. In the foundational terminology established by Donald E. Knuth in The Art of Computer Programming, every legitimate algorithm must rigorously satisfy five fundamental criteria:

CODECopy Code
+-------------------------------------------------------------------------+
|                  KNUTH'S FIVE FOUNDATIONAL CRITERIA                     |
|                                                                         |
|  1. FINITENESS    : Must terminate after a finite number of operations. |
|  2. DEFINITENESS  : Every instruction must be unambiguous and clear.    |
|  3. INPUT         : Zero or more valid quantities externally supplied.  |
|  4. OUTPUT        : One or more outputs mathematically related to input.|
|  5. EFFECTIVENESS : Operations must be basic enough to be done exactly  |
|                     in finite time with pencil and paper.               |
+-------------------------------------------------------------------------+

1.1 Program vs. Algorithm

A Program is the concrete implementation of an algorithm written in a specific programming language (such as C, Java, or Python) tied to compiler syntax and machine architectures. An Algorithm, by contrast, is an abstract, mathematical specification independent of hardware, memory limits, operating system, or syntax. An operating system kernel or server daemon that runs indefinitely without terminating is a computational process or program, but strictly speaking not an algorithm under Knuth's finiteness constraint.

1.2 Algorithmic Problem Solving Lifecycle

The standard methodology for developing efficient computational solutions involves systematic phases:

1. Problem Formulation: Precise specification of domain constraints, valid input sets, and required output predicates.
2. Computational Model Selection: Adopting an abstract hardware execution model—predominantly the Random Access Machine (RAM) model, where operations (arithmetic, logic, memory dereference) execute in uniform unit time $O(1)$.
3. Algorithmic Strategy Selection: Choosing an appropriate paradigm (Divide-and-Conquer, Greedy, Dynamic Programming).
4. Data Structure Design: Coupling the algorithm with optimal representations (Heaps, Balanced BSTs, Hash Maps, Disjoint Sets).
5. Formal Correctness Proof: Proving that the algorithm terminates and produces mathematically correct outputs for all valid inputs using Loop Invariants and Mathematical Induction.
6. Complexity Analysis: Evaluating asymptotic time and space upper/lower bounds.
7. Implementation & Empirical Profiling: Translating into robust code and bench-testing across synthetic and adversarial test suites.

2. Loop Invariants & Mathematical Proof of Correctness

To prove that an iterative algorithm computes the correct result, computer scientists utilize Loop Invariants. A loop invariant is a formal logical predicate that remains true prior to the loop, across every iteration, and upon loop termination.

CODECopy Code
+-------------------------------------------------------------------------+
|                      LOOP INVARIANT INDUCTION STEPS                     |
|                                                                         |
|  1. INITIALIZATION : Invariant is TRUE prior to the first iteration.    |
|  2. MAINTENANCE    : If TRUE before an iteration, it remains TRUE       |
|                      before the subsequent iteration (Inductive Step).  |
|  3. TERMINATION    : When the loop terminates, the invariant provides a |
|                      useful property showing that the algorithm is      |
|                      mathematically correct.                            |
+-------------------------------------------------------------------------+

2.1 Case Study: Insertion Sort Invariant Proof

Consider sorting an array $A[1 \dots n]$. In Insertion Sort, the outer loop advances an index $j$ from $2$ to $n$:

• Loop Invariant: At the start of each iteration of the outer for loop, the subarray $A[1 \dots j-1]$ consists of the elements originally in $A[1 \dots j-1]$, but in sorted order.
• Initialization: Prior to the first iteration ($j = 2$), the subarray $A[1 \dots j-1]$ is simply $A[1]$, which contains a single element. A single-element array is trivially sorted. Invariant holds.
• Maintenance: The body of the outer loop moves $A[j-1], A[j-2], \dots$ to the right until the proper position for $A[j]$ is identified, inserting the key. Subarray $A[1 \dots j]$ now contains the original elements in sorted order. Incrementing $j$ restores the invariant for the next iteration.
• Termination: The loop terminates when $j > n$, meaning $j = n + 1$. Substituting $j = n + 1$ into the invariant statement yields: the subarray $A[1 \dots n]$ consists of the original elements in fully sorted order. Hence, the algorithm is proven correct.

3. Asymptotic Analysis & Formal Notations

Asymptotic analysis evaluates how the resource consumption (execution time or memory space) of an algorithm scales as the input size $n$ approaches infinity ($n \to \infty$). It abstracts away hardware-dependent clock frequencies, operating system scheduling, compiler optimizations, and constant factors.

CODECopy Code
             ASYMPTOTIC BOUNDS VISUALIZATION
   f(n)
    ^
    |                                   c2 * g(n)  [Upper Bound]
    |                                 /
    |                   f(n)        /
    |                     \       /
    |                       \   /
    |                        X
    |                      /   \
    |                    /       \      c1 * g(n)  [Lower Bound]
    |                  /           \  /
    |                 /             /
    |                /            /
    +---------------+------------+-------------------------> n
    0               n0           n

3.1 Formal Mathematical Definitions

1. Big-O Notation ($O$): Asymptotic Upper Bound

$O(g(n)) = \{ f(n) : \exists \text{ positive constants } c > 0 \text{ and } n_0 > 0 \text{ such that } 0 \le f(n) \le c \cdot g(n) \text{ for all } n \ge n_0 \}$
Big-O characterizes the worst-case growth rate; $f(n)$ grows no faster than $g(n)$ for sufficiently large $n$.

2. Big-Omega Notation ($\Omega$): Asymptotic Lower Bound

$\Omega(g(n)) = \{ f(n) : \exists \text{ positive constants } c > 0 \text{ and } n_0 > 0 \text{ such that } 0 \le c \cdot g(n) \le f(n) \text{ for all } n \ge n_0 \}$
Big-Omega establishes the minimum resources required; $f(n)$ grows at least as fast as $g(n)$.

3. Big-Theta Notation ($\Theta$): Asymptotically Tight Bound

$\Theta(g(n)) = \{ f(n) : \exists \text{ positive constants } c_1 > 0, c_2 > 0, \text{ and } n_0 > 0 \text{ such that } 0 \le c_1 \cdot g(n) \le f(n) \le c_2 \cdot g(n) \text{ for all } n \ge n_0 \}$
Theorem: $f(n) = \Theta(g(n)) \iff f(n) = O(g(n)) \text{ and } f(n) = \Omega(g(n))$.

4. Little-o Notation ($o$): Strict Asymptotic Upper Bound

$o(g(n)) = \{ f(n) : \forall c > 0, \exists n_0 > 0 \text{ such that } 0 \le f(n) < c \cdot g(n) \text{ for all } n \ge n_0 \}$
Equivalently: $\lim_{n \to \infty} \frac{f(n)}{g(n)} = 0$. $f(n)$ becomes insignificant relative to $g(n)$ as $n \to \infty$.

5. Little-omega Notation ($\omega$): Strict Asymptotic Lower Bound

$\omega(g(n)) = \{ f(n) : \forall c > 0, \exists n_0 > 0 \text{ such that } 0 \le c \cdot g(n) < f(n) \text{ for all } n \ge n_0 \}$
Equivalently: $\lim_{n \to \infty} \frac{f(n)}{g(n)} = \infty$.

3.2 Limit Quotient Rule for Comparing Orders of Growth

To compare the asymptotic orders of two functions $f(n)$ and $g(n)$, evaluate the limit of their ratio using L'Hôpital's Rule where appropriate:
$L = \lim_{n \to \infty} \frac{f(n)}{g(n)}$

• If $L = 0 \implies f(n) = o(g(n))$ and $f(n) = O(g(n))$.
• If $L = c$ (where $0 < c < \infty$) $\implies f(n) = \Theta(g(n))$.
• If $L = \infty \implies f(n) = \omega(g(n))$ and $f(n) = \Omega(g(n))$.
• If the limit does not exist and oscillates (e.g., $f(n) = n^{1 + \sin n}$), the functions are asymptotically incomparable.

4. Hierarchy of Fundamental Efficiency Classes

In algorithm design, standard complexity functions form a strict ascending order of growth:
$1 \prec \log \log n \prec \log n \prec \sqrt{n} \prec n \prec n \log n \prec n^2 \prec n^3 \prec 2^n \prec e^n \prec n! \prec n^n$

5. Recurrence Relations & Divide-and-Conquer Analysis

Divide-and-conquer algorithms divide a problem of size $n$ into $a$ subproblems, each of size $n/b$, solve them recursively, and combine their solutions in $f(n)$ time:
$T(n) = a T(n/b) + f(n)$

5.1 The Master Theorem (CLRS Formulation)

Let $a \ge 1$ and $b > 1$ be constants, and let $f(n)$ be an asymptotically positive function. Compare $f(n)$ against the watershed function $n^{\log_b a}$:

CODECopy Code
+----------------------------------------------------------------------------------------------------+
|                                    MASTER THEOREM (THREE CASES)                                    |
|                                                                                                    |
|  CASE 1: If f(n) = O(n^(log_b(a) - epsilon)) for some constant epsilon > 0,                        |
|          then T(n) = Theta(n^(log_b a)).  [Leaves dominate computational cost]                     |
|                                                                                                    |
|  CASE 2: If f(n) = Theta(n^(log_b a) * log^k(n)) for some k >= 0,                                  |
|          then T(n) = Theta(n^(log_b a) * log^(k+1)(n)).  [Work distributed evenly across levels]  |
|                                                                                                    |
|  CASE 3: If f(n) = Omega(n^(log_b(a) + epsilon)) for some constant epsilon > 0,                     |
|          AND the Regularity Condition holds: a * f(n/b) <= c * f(n) for some c < 1 and large n,   |
|          then T(n) = Theta(f(n)).  [Root / combination step dominates computational cost]          |
+----------------------------------------------------------------------------------------------------+

Detailed Examples:

1. Merge Sort: $T(n) = 2T(n/2) + \Theta(n)$
   • $a = 2, b = 2 \implies n^{\log_2 2} = n^1 = n$.
   • $f(n) = \Theta(n) \implies$ Case 2 with $k = 0$.
   • Solution: $T(n) = \Theta(n \log n)$.
2. Strassen's Matrix Multiplication: $T(n) = 7T(n/2) + \Theta(n^2)$
   • $a = 7, b = 2 \implies n^{\log_2 7} \approx n^{2.807}$.
   • $f(n) = n^2 = O(n^{2.807 - \epsilon})$ with $\epsilon \approx 0.807 \implies$ Case 1.
   • Solution: $T(n) = \Theta(n^{\log_2 7}) \approx \Theta(n^{2.81})$.
3. Binary Search: $T(n) = T(n/2) + \Theta(1)$
   • $a = 1, b = 2 \implies n^{\log_2 1} = n^0 = 1$.
   • $f(n) = \Theta(1) = \Theta(n^0) \implies$ Case 2 with $k = 0$.
   • Solution: $T(n) = \Theta(\log n)$.

5.2 Pitfalls of the Master Theorem

The Master Theorem does not apply if:

• $T(n) = 2T(n/2) + n \log n$: Here $f(n)$ is larger than $n^{\log_2 2} = n$, but not polynomially larger (it lacks the factor $n^\epsilon$). Solved using recursion trees: $\Theta(n \log^2 n)$.
• $T(n) = 2T(n/2) + \frac{n}{\log n}$: $f(n)$ is smaller by a logarithmic factor, not polynomial $n^{-\epsilon}$. Solved using substitution: $\Theta(n \log \log n)$.
• $a < 1$ or $b \le 1$.
• Non-constant subproblem sizes (e.g., $T(n) = T(n/3) + T(2n/3) + n$), which require the Akra-Bazzi method or recursion trees.

6. Amortized Analysis Techniques

In many stateful data structures, an occasional operation is very expensive, but the majority of operations are extremely fast. Amortized Analysis guarantees the average performance of each operation over a worst-case sequence of operations without probabilistic assumptions.

CODECopy Code
+-------------------------------------------------------------------------+
|                  THREE METHODS OF AMORTIZED ANALYSIS                    |
|                                                                         |
|  1. AGGREGATE METHOD : Show that a sequence of n operations takes       |
|                        T(n) worst-case time in total.                   |
|                        Amortized cost per operation = T(n) / n.         |
|                                                                         |
|  2. ACCOUNTING METHOD: Assign artificial charges (amortized costs)      |
|                        to each operation. Overcharges are stored as     |
|                        credit to pay for future expensive operations.   |
|                        Credit must never drop below zero!               |
|                                                                         |
|  3. POTENTIAL METHOD : Define a potential function Phi(D) mapping data  |
|                        structure states to real numbers.                |
|                        Amortized cost: a_i = c_i + Phi(D_i) - Phi(D_i-1)|
+-------------------------------------------------------------------------+

6.1 Case Study: Dynamic Table Expansion

Consider a dynamic array that doubles in capacity whenever an insertion occurs in a full table.

• Cost: If table is not full, cost is $1$ (insert element). If full (capacity $m$), allocating array of size $2m$, copying $m$ elements, and inserting takes $m + 1$ operations.
• Accounting Method: Assign an amortized cost of \3$ to each insertion:
  • \1$ pays for inserting the element into the current slot.
  • \1$ pays for moving this element when the table doubles in the future.
  • \1$pays for moving one of the older elements that already used up its credit. When capacity doubles from$m$to$2m$, exactly$m$insertions have occurred since the last doubling, accumulating$$2m$in credit—precisely enough to pay for copying all$m$elements! Hence, amortized cost per insertion is strictly$O(1)$.

7. Fundamental Data Structures & Asymptotic Complexities

*Insertion and deletion at head or with known pointer.