MODULE 1

Algorithm
Basics
Definition & Characteristics • Design Techniques • Recurrence Relations

Design & Analysis of Algorithms

Module Outline
What we cover in Module 1

Algorithm Definition Substitution Method

01 05
What it is, why it matters Guess, prove by induction

Characteristics Recursion Tree Method

02 06
5 key properties every algorithm must have Visualise recursive call costs

Design Techniques Master Method

03 07
Divide & Conquer, DP, Greedy & more Master theorem — the fast lane

Recurrence Relations
04
Modeling recursive time complexity
DEFINITION 01

What is an Algorithm?
"An algorithm is a well-defined, finite sequence of computational steps that takes some value (or set of values)
as input and produces some value (or set of values) as output."

Input Output Process

Zero or more well-defined inputs taken from a A deterministic, step-by-step transformation

One or more results produced from given inputs
specified set mechanism

Example: Finding the maximum of two numbers

MAX(A, B): if A ≥ B → return A else → return B

CHARACTERISTICS

5 Essential Properties
Every valid algorithm must satisfy ALL of the following

Input Finiteness
1 Has zero or more inputs — may accept data from an external
4 Must terminate after a finite number of steps — infinite loops
source or none at all (e.g., print "Hello") are NOT valid algorithms

Output Effectiveness
2 Produces at least one output — the result or answer that the
5 Every step must be basic, feasible and performable with pen
algorithm computes or returns and paper — no oracle or infinite-precision ops

Definiteness
3 Each step is precisely and unambiguously defined — no
vagueness or room for interpretation in any instruction
DESIGN TECHNIQUES 03

Algorithm Design Techniques

Divide & Conquer Dynamic Programming

Break into sub-problems, solve recursively, combine. e.g., Merge Sort, Quick Sort, Solve overlapping sub-problems once and store results (memoisation /
Binary Search tabulation). e.g., Fibonacci, Knapsack

Greedy Method Backtracking

Make locally optimal choice at each step hoping to find global optimum. e.g., Try all options; abandon a path as soon as it violates constraints. e.g., N-Queens,
Kruskal, Huffman, Dijkstra Sudoku, Hamiltonian

Branch & Bound Brute Force

Explore solution tree with bounds to prune unpromising branches. e.g., TSP, 0/1 Try every possible solution exhaustively. Simple but often inefficient. e.g., Linear
Knapsack optimisation Search, Bubble Sort
RECURRENCE RELATIONS 04

Recurrence Relations
Mathematical equations that describe the running time of a recursive algorithm

A recurrence relation defines T(n) — the time for input of size n — in terms of T(k) for smaller k, plus work done at the
current level.

T(n) = T(n/2) + O(1)

Binary Search
One recursive call on half the input, O(1) work per level

T(n) = 2T(n/2) + O(n)

Merge Sort
Two recursive calls on halves, O(n) merge work at each level

T(n) = T(n-1) + T(n-2) + O(1)

Fibonacci (naïve)
Two overlapping sub-problems, exponential blowup

Methods to Solve: Substitution Method • Recursion Tree Method • Master Method

SUBSTITUTION METHOD 05

Substitution Method
Make a Guess
1 Guess the form of the solution, e.g. T(n) = O(n log n)

Prove by Mathematical Induction

2 Assume T(k) ≤ c·f(k) for all k < n, then show T(n) ≤ c·f(n)

Solve for Constants

3 Find constants c and n₀ > 0 such that T(n) ≤ c·f(n) for all n ≥ n₀

Worked Example
Given: T(n) = 2T(n/2) + n, T(1) = 1
Guess: T(n) = O(n log n) → Assume T(k) ≤ ck log k for all k < n
Prove: T(n) = 2T(n/2)+n ≤ 2c(n/2)log(n/2)+n = cn·log n − cn + n ≤ cn log n ✓
RECURSION TREE METHOD 06

Recursion Tree Method

Visualise the recursive call structure as a tree — sum each level’s cost

Draw the Tree T(n) = 2T(n/2) + n

1 Expand T(n) by substituting the recurrence. Each node represents cost at that call.
T(n) =n

Cost Per Level

2 Sum the work done at each level of the tree. Often the level cost is constant or geometric. T(n/2) = n/2 T(n/2) = n/2

Count Levels
T(n/4) T(n/4) T(n/4) T(n/4)
3 Determine the height of the tree — depth until base case is reached (usually log n or n).
…
Level 0: n | Level 1: n | Level 2: n | ⋯ |
Sum All Levels Height: log n
4 Total cost = (cost per level) × (number of levels). This gives the asymptotic bound.
Total = n × log n = O(n log n)

Best used when the recurrence has unequal sub-problems or non-standard branching factors
MASTER METHOD 07

Master Theorem
Standard Form: T(n) = aT(n/b) + f(n) where a ≥ 1, b > 1, f(n) is asymptotically positive

If: f(n) = O(n^(log_b a − ε)) for some ε > 0

Case 1 Then: T(n) = Θ(n^(log_b a)) — Work dominated by leaves of recursion tree
e.g. T(n)=8T(n/2)+n² → log₂8=3, n²=O(n^(3−1)) → T(n)=Θ(n³)

If: f(n) = Θ(n^(log_b a) · log^k n) for k ≥ 0

Case 2 Then: T(n) = Θ(n^(log_b a) · log^(k+1) n) — Work evenly split at each level of recursion
e.g. T(n)=2T(n/2)+n → log₂2=1, f(n)=Θ(n¹) → T(n)=Θ(n log n)

If: f(n) = Ω(n^(log_b a + ε)) for some ε > 0

Case 3 Then: T(n) = Θ(f(n)) — Work dominated by root (top-level cost)

e.g. T(n)=2T(n/2)+n² → log₂2=1, n²=Ω(n^(1+1)) → T(n)=Θ(n²)

Master theorem does NOT apply if f(n) is not polynomially larger/smaller than n^(log_b a)
QUICK REFERENCE

Common Recurrence Results

Master Theorem applied to frequently used algorithms

Recurrence a|b log_b(a) f(n) Case Result Algorithm

T(n)=2T(n/2)+n 2|2 1 n Case 2 Θ(n log n) Merge Sort

T(n)=T(n/2)+1 1|2 0 O(1) Case 2 Θ(log n) Binary Search

T(n)=8T(n/2)+n² 8|2 3 n² Case 1 Θ(n³) Matrix Mult.

T(n)=4T(n/2)+n² 4|2 2 n² Case 2 Θ(n² log n) Strassen-like

T(n)=2T(n/2)+n² 2|2 1 n² Case 3 Θ(n²) —

Substitution: Flexible, requires clever guess | Recursion Tree: Visual, intuitive | Master Method: Fastest — plug and solve
MODULE 1 — SUMMARY

Key Takeaways
Algorithm Definition Recurrence Relations

A finite, definite, and effective step-by-step procedure that solves a Express T(n) recursively. Solved via: Substitution (induction), Recursion
problem — always terminates and produces output. Tree (visual), or Master Method (formulaic).

5 Characteristics Master Theorem

Input · Output · Definiteness · Finiteness · Effectiveness — all five must T(n) = aT(n/b)+f(n): Compare f(n) with n^log_b(a) to classify into Case
be satisfied for a procedure to be an algorithm. 1, 2, or 3 and read off the bound.

Design Techniques

D&C · DP · Greedy · Backtracking · Branch & Bound — each suited to a

different class of problems.

Next: Module 2 — Sorting Algorithms & Time Complexity Analysis