Exam Practice

Master algorithm efficiency analysis, recurrences, combinatorial generation, divide-and-conquer, and midterm exam problems based on Levitin (3rd ed).

Reference text: Introduction to the Design and Analysis of Algorithms, 3rd Edition (Anany Levitin)

Master Theorem Reference: $T(n) = a T(n/b) + \Theta(n^d)$

Condition	Resulting Complexity $T(n)$	Dominant Phase	Example Algorithm
$a < b^d$	$\Theta(n^d)$	Root-dominated (combining)	$\text{D\&C: } T(n) = 2T(n/2) + n^2 \implies \Theta(n^2)$
$a = b^d$	$\Theta(n^d \log n)$	Balanced across all tree levels	$\text{Merge Sort: } 2T(n/2) + n \implies \Theta(n \log n)$
$a > b^d$	$\Theta(n^{\log_b a})$	Leaf-dominated (subproblems)	$\text{Karatsuba: } 3T(n/2) + n \implies \Theta(n^{1.585})$

Algorithm Complexities Summary (Chapters 1–5)

Algorithm	Design Strategy	Best Case	Average Case	Worst Case	Space
Sieve of Eratosthenes	Brute Force / Elimination	$\Theta(n \log \log n)$	$\Theta(n \log \log n)$	$\Theta(n \log \log n)$	$\Theta(n)$
Selection Sort	Brute Force	$\Theta(n^2)$	$\Theta(n^2)$	$\Theta(n^2)$	$\Theta(1)$
Bubble Sort	Brute Force	$\Theta(n)$	$\Theta(n^2)$	$\Theta(n^2)$	$\Theta(1)$
Insertion Sort	Decrease-by-1	$\Theta(n)$	$\Theta(n^2)$	$\Theta(n^2)$	$\Theta(1)$
Sequential String Match	Brute Force	$\Theta(n)$	$\Theta(n)$	$\Theta(n \cdot m)$	$\Theta(1)$
2D Board Match	Brute Force	$\Theta(R \cdot C)$	$\Theta(R \cdot C)$	$\Theta(R \cdot C \cdot m)$	$\Theta(1)$
Closest Pair (Brute Force)	Brute Force	$\Theta(n^2)$	$\Theta(n^2)$	$\Theta(n^2)$	$\Theta(1)$
Convex Hull (Brute Force)	Brute Force	$\Theta(n^3)$	$\Theta(n^3)$	$\Theta(n^3)$	$\Theta(1)$
TSP (Exhaustive Search)	Exhaustive Search	$\Theta(n!)$	$\Theta(n!)$	$\Theta(n!)$	$\Theta(n)$
Knapsack (Exhaustive)	Exhaustive Search	$\Theta(2^n)$	$\Theta(2^n)$	$\Theta(2^n)$	$\Theta(n)$
Assignment Problem	Exhaustive Search	$\Theta(n!)$	$\Theta(n!)$	$\Theta(n!)$	$\Theta(n)$
Tower of Hanoi	Decrease-by-1 / D&C	$\Theta(2^n)$	$\Theta(2^n)$	$\Theta(2^n)$	$\Theta(n)$
Binary Search	Decrease-by-factor-2	$\Theta(1)$	$\Theta(\log n)$	$\Theta(\log n)$	$\Theta(1)$
Euclid GCD	Variable-Size Decrease	$\Theta(1)$	$\Theta(\log n)$	$\Theta(\log n)$	$\Theta(1)$
Merge Sort	Divide-and-Conquer	$\Theta(n \log n)$	$\Theta(n \log n)$	$\Theta(n \log n)$	$\Theta(n)$
Quick Sort	Divide-and-Conquer	$\Theta(n \log n)$	$\Theta(n \log n)$	$\Theta(n^2)$	$\Theta(\log n)$
Closest Pair (D&C)	Divide-and-Conquer	$\Theta(n \log n)$	$\Theta(n \log n)$	$\Theta(n \log n)$	$\Theta(n)$
Karatsuba Multiplication	Divide-and-Conquer	$\Theta(n^{1.585})$	$\Theta(n^{1.585})$	$\Theta(n^{1.585})$	$\Theta(\log n)$
Strassen Matrix Mult	Divide-and-Conquer	$\Theta(n^{2.807})$	$\Theta(n^{2.807})$	$\Theta(n^{2.807})$	$\Theta(n^2)$

Essential Summation Formulas & Recurrence Identities

Sum of First

n

Integers

\sum_{i=1}^n i = \frac{n(n+1)}{2} \approx \frac{n^2}{2} \in \Theta(n^2)

Sum of Squares

\sum_{i=1}^n i^2 = \frac{n(n+1)(2n+1)}{6} \approx \frac{n^3}{3} \in \Theta(n^3)

Finite Geometric Series

\sum_{i=0}^n a^i = \frac{a^{n+1} - 1}{a - 1} \quad (a \ne 1)

Halving Recurrence

T(n) = T(n/2) + 1 \implies T(n) = \lfloor \log_2 n \rfloor + 1 \in \Theta(\log n)

Doubling Recurrence

T(n) = 2T(n-1) + 1 \implies T(n) = 2^n - 1 \in \Theta(2^n)

Merge Sort Recurrence

T(n) = 2T(n/2) + \Theta(n) \implies T(n) \in \Theta(n \log n)

Exam Practice

Master Theorem Reference: T(n)=aT(n/b)+Θ(nd)T(n) = a T(n/b) + \Theta(n^d)T(n)=aT(n/b)+Θ(nd)

Algorithm Complexities Summary (Chapters 1–5)

Essential Summation Formulas & Recurrence Identities

Master Theorem Reference: $T(n) = a T(n/b) + \Theta(n^d)$