PPT: Recurrence Relations | Algorithms - Computer Science Engineering (CSE) PDF Download

 Page 1


Recurrence 
Relations
Page 2


Recurrence 
Relations
Introduction 
Definition
A recurrence relation is an 
equation that defines a 
sequence recursively, where 
each term is expressed in terms 
of previous terms. 
Purpose
These relations are fundamental 
in algorithm analysis, helping us 
model the running time or 
space complexity of recursive 
algorithms.
General Form
The general form is 
T(n) = a * T(n/b) + f(n), 
Where T(n) represents the total 
running time for input size n, a is 
the number of subproblems, n/b 
is the size of each subproblem, 
and f(n) is the cost of non-
recursive work.
Recurrence relations are particularly useful for analyzing divide-and-conquer, recursive, and iterative 
algorithms. 
Page 3


Recurrence 
Relations
Introduction 
Definition
A recurrence relation is an 
equation that defines a 
sequence recursively, where 
each term is expressed in terms 
of previous terms. 
Purpose
These relations are fundamental 
in algorithm analysis, helping us 
model the running time or 
space complexity of recursive 
algorithms.
General Form
The general form is 
T(n) = a * T(n/b) + f(n), 
Where T(n) represents the total 
running time for input size n, a is 
the number of subproblems, n/b 
is the size of each subproblem, 
and f(n) is the cost of non-
recursive work.
Recurrence relations are particularly useful for analyzing divide-and-conquer, recursive, and iterative 
algorithms. 
Types of Recurrence Relations
Recurrence relations come in various forms, each suited to different algorithmic patterns. Understanding these 
types helps in selecting the appropriate solution method and analyzing algorithm efficiency accurately.
Linear recurrence relations can be homogeneous (without non-recursive terms) or non-homogeneous (including 
non-recursive terms). Divide-and-conquer recurrences follow the form T(n) = a * T(n/b) + f(n), while decreasing 
function recurrences involve subtraction in recursive terms.
Linear Recurrence Relations
Homogeneous: T(n) = 2T(n-1)
Non-Homogeneous: T(n) = T(n-1) + n
Divide-and-Conquer
Form: T(n) = a * T(n/b) + f(n)
Example: T(n) = 2T(n/2) + n
Other Forms
Decreasing: T(n) = T(n-1) + 1
Logarithmic: T(n) = T(n-1) + log n
Root Function: T(n) = T(:n) + 1
Page 4


Recurrence 
Relations
Introduction 
Definition
A recurrence relation is an 
equation that defines a 
sequence recursively, where 
each term is expressed in terms 
of previous terms. 
Purpose
These relations are fundamental 
in algorithm analysis, helping us 
model the running time or 
space complexity of recursive 
algorithms.
General Form
The general form is 
T(n) = a * T(n/b) + f(n), 
Where T(n) represents the total 
running time for input size n, a is 
the number of subproblems, n/b 
is the size of each subproblem, 
and f(n) is the cost of non-
recursive work.
Recurrence relations are particularly useful for analyzing divide-and-conquer, recursive, and iterative 
algorithms. 
Types of Recurrence Relations
Recurrence relations come in various forms, each suited to different algorithmic patterns. Understanding these 
types helps in selecting the appropriate solution method and analyzing algorithm efficiency accurately.
Linear recurrence relations can be homogeneous (without non-recursive terms) or non-homogeneous (including 
non-recursive terms). Divide-and-conquer recurrences follow the form T(n) = a * T(n/b) + f(n), while decreasing 
function recurrences involve subtraction in recursive terms.
Linear Recurrence Relations
Homogeneous: T(n) = 2T(n-1)
Non-Homogeneous: T(n) = T(n-1) + n
Divide-and-Conquer
Form: T(n) = a * T(n/b) + f(n)
Example: T(n) = 2T(n/2) + n
Other Forms
Decreasing: T(n) = T(n-1) + 1
Logarithmic: T(n) = T(n-1) + log n
Root Function: T(n) = T(:n) + 1
Methods to Solve Recurrence Relations
Several methods exist for solving recurrence relations, each with its strengths and suitable applications. The choice 
of method depends on the structure and complexity of the recurrence relation at hand.
Substitution 
Method
Guess solution and 
prove it using 
induction. Suitable 
for simple 
recurrences.
Recursion Tree 
Method
Visualize recursion 
as a tree; sum costs 
at each level. 
Useful for divide-
and-conquer.
Master 
Theorem
Formula for 
recurrences of the 
form T(n) = a * 
T(n/b) + f(n). Fast 
for standard 
problems.
Iteration 
Method
Expand recurrence 
iteratively and sum 
terms. Works well 
for linear 
recurrences.
Page 5


Recurrence 
Relations
Introduction 
Definition
A recurrence relation is an 
equation that defines a 
sequence recursively, where 
each term is expressed in terms 
of previous terms. 
Purpose
These relations are fundamental 
in algorithm analysis, helping us 
model the running time or 
space complexity of recursive 
algorithms.
General Form
The general form is 
T(n) = a * T(n/b) + f(n), 
Where T(n) represents the total 
running time for input size n, a is 
the number of subproblems, n/b 
is the size of each subproblem, 
and f(n) is the cost of non-
recursive work.
Recurrence relations are particularly useful for analyzing divide-and-conquer, recursive, and iterative 
algorithms. 
Types of Recurrence Relations
Recurrence relations come in various forms, each suited to different algorithmic patterns. Understanding these 
types helps in selecting the appropriate solution method and analyzing algorithm efficiency accurately.
Linear recurrence relations can be homogeneous (without non-recursive terms) or non-homogeneous (including 
non-recursive terms). Divide-and-conquer recurrences follow the form T(n) = a * T(n/b) + f(n), while decreasing 
function recurrences involve subtraction in recursive terms.
Linear Recurrence Relations
Homogeneous: T(n) = 2T(n-1)
Non-Homogeneous: T(n) = T(n-1) + n
Divide-and-Conquer
Form: T(n) = a * T(n/b) + f(n)
Example: T(n) = 2T(n/2) + n
Other Forms
Decreasing: T(n) = T(n-1) + 1
Logarithmic: T(n) = T(n-1) + log n
Root Function: T(n) = T(:n) + 1
Methods to Solve Recurrence Relations
Several methods exist for solving recurrence relations, each with its strengths and suitable applications. The choice 
of method depends on the structure and complexity of the recurrence relation at hand.
Substitution 
Method
Guess solution and 
prove it using 
induction. Suitable 
for simple 
recurrences.
Recursion Tree 
Method
Visualize recursion 
as a tree; sum costs 
at each level. 
Useful for divide-
and-conquer.
Master 
Theorem
Formula for 
recurrences of the 
form T(n) = a * 
T(n/b) + f(n). Fast 
for standard 
problems.
Iteration 
Method
Expand recurrence 
iteratively and sum 
terms. Works well 
for linear 
recurrences.
Iteration Method
The iteration method expands the recurrence iteratively and sums the terms to find a closed-form solution. This 
approach is particularly effective for linear recurrences with constant or simple non-recursive terms.
The process involves writing T(n) in terms of previous terms, identifying a pattern, and expressing the sum in closed 
form. For example, with T(n) = T(n-1) + 1 and T(1) = 1, we can expand to T(n) = T(n-1) + 1 = T(n-2) + 1 + 1 = ... = T(1) + (n-1)*1, 
which simplifies to T(n) = n with O(n) time complexity.
Write Recursive 
Expansion
Express T(n) in terms of 
T(n-1), T(n-2), etc.
Identify Pattern
Recognize the pattern 
in the expanded terms
Sum the Series
Calculate the sum of all 
terms in the expansion
Express in Closed 
Form
Simplify to a non-
recursive mathematical 
expression