Academic Session 2025-26

ODD Semester Jul-Dec 2025

UNIVERSITY INSTITUTE OF ENGINEERING
CSE-2nd year
CS201/IT201
SEMESTER 3
Advanced Data Structures and Algorithms
(24CSH-202)

Unit No. 1 Chapter No. 1.1.3 Topic : Recurrence Relations

____________________________________________________
Faculty Name and E_Code: Bhavneet Kaur(E14414)
Designation: Assistant Professor, Master Subject Co-ordinator
 Learning Objectives

• Understand and Define Recurrence Relations

• Apply Recursion Tree and Substitution Methods

• Use the Master Theorem to Solve Recurrences

2
 Recurrence Relation Common in
divide-and- Useful in Merge
conquer Sort, Binary
Search, etc.
• Describes succession of values
by reference to the terms that
came before it.
• Representation of every term in
the series as a function of the
terms that came before it.
• Equations that define sequences
recursively.
• Used to describe running time of recursive
A recurrence relation is an equation which is
algorithms. defined in terms of itself.
An equation or inequality that characterises a
function in terms of its value on smaller
inputs is called a recurrence. 3
 Solving the Recurrence Relation

An equation or inequality that describes a function in

terms of its value on smaller inputs.
T(n) = T(n-1) + n

What is the actual running time of the algorithm?

1.Need to solve the recurrence
2.Find an explicit formula of the expression
3.Bound the recurrence by an expression that involves n.
4
 Example Recurrences
• T(n) = T(n-1) + n
Θ(n2)
– Recursive algorithm that loops through the input to eliminate
one item
• T(n) = T(n/2) + c
Θ(lgn)
– Recursive algorithm that halves the input in one step
• T(n) = T(n/2) + n
Θ(n)
– Recursive algorithm that halves the 5input but must examine
every item in the input
• T(n) = 2T(n/2) + 1 Θ(n) 5
 Recurrent Algorithms
-BINARY-SEARCH
• For an ordered array A, finds if x is in the array A[lo…hi]

BINARY-SEARCH (A, lo, hi, x)

if (lo > hi) 1 2 3 4 5 6 7 8

return FALSE 2 3 5 7 9 10 11 12
mid  (lo+hi)/2
if x = A[mid] mid
lo hi
return TRUE
if ( x < A[mid] )
BINARY-SEARCH (A, lo, mid-1, x)
if ( x > A[mid] )
BINARY-SEARCH (A, mid+1, hi, x)

6
 Recurrent Algorithms
-BINARY-SEARCH(Contd.)

Input Size is n

7
Methods to Solve Recurrence Relations

Substitution Recursion Tree

Master Method
Method Method
• Guess solution • Visualize • Form: T(n) =
and prove by recurrence as a aT(n/b) + f(n)
induction tree
• Example: • Sum cost across
T(n) = 2T(n/2) + n all levels
→ O(n log n) • Example:
• T(n) = 2T(n/2) +
n → O(n log n)

8
The recursion-tree method

Convert the recurrence into a tree:

– Each node represents the cost incurred at various
levels of recursion
– Sum up the costs of all levels

9
The recursion-tree method(Contd.)
In a recursion-tree,
 Each node represents the cost of a single
sub-problem somewhere in the set of
recursive function invocations.
 We sum the costs within each level of the
tree to obtain a set of per-level costs.
 Then we sum all the per-level cost to
determine the total cost of all levels of the
recursion.
Recursion trees are particularly useful when the
recurrence describes the running time of a divide-
and-conquer algorithm.
Example 1: Recursion Tree for T(n)=2T(n/2)+n
Structure of the Tree: Cost at Each Level:
•Level 0: n
Level 0: T(n) •Level 1: 2 × (n/2) = n
•Level 2: 4 × (n/4) = n
/ \ •…
Level 1: T(n/2) T(n/2) •Level log n: n
/ \ / \
Total Cost:
Level 2: T(n/4) T(n/4) •log⁡2n+1\log_2 n + 1log2​n+1 levels
T(n/4) T(n/4) •Work per level: n
•Total = n⋅log⁡2nn \cdot \log_2 nn⋅log2​n
...
Level log n: T(1) T(1) ... (n Final Complexity:
leaves) T(n)=Θ(nlog⁡n)
 Example 2: Recursion Tree for T(n) =
T(n/5) + T(4n/5) + n
2. T(n)
1: Break the Problem Recursively / \
At each level: T(n/5) T(4n/5)
•Total work outside recursion is n / \ / \
•Recursive calls go to T(n/5) and T(4n/5) ... ... T(4²n/5²) ...

3: Estimate Tree Height 4: Total Work

Let’s track the largest subproblem size at each level: •Each level does Θ(n) total work
•Level 0: n
(sum of both branches is ≤ n)
•Level 1: 4n/5 •There are Θ(log n) levels
•Level 2: (4/5)²·n
•Level k: (4/5)^k·n Final Answer
Set: T(n)=Θ(nlog⁡n)T(n) = \Theta(n \log n)T(n)=Θ(nlogn)
So the height of the tree is Θ(log⁡n)
 Substitution Method

 Expand the recurrence k times

 Work some algebra to express as a summation
 Evaluate the summation
 Convert the recurrence into a summation and
try to bound it using known series
Iterate the recurrence until the initial condition is
reached.
Use back-substitution to express the recurrence in
terms of n and the initial (boundary) condition.
 Example
Step 1: Understand the recurrence
The recurrence means that to solve a problem of size n, you
break it into two subproblems of size n/2, solve each
recursively, and then do an additional n amount of work to
combine the results.
Step 2: Guess the form of the solution
Since this is a common divide and conquer recurrence, a good
guess is:
T(n) = O(n log n)
This means the time grows roughly like n times the logarithm of
n.
Step 3: Use the substitution method to prove the guess
We want to prove by induction that:
T(n) ≤ c * n * log n for some constant c > 0 and for all n ≥ 1.
Step 4: Base case
For n = 1, the problem takes constant time:
T(1) = Θ(1) ≤ c * 1 * log 1 = 0
Since log 1 = 0, this holds for some constant c.
 Example

Step 5: Inductive step

Step 6: Simplify and finalize
Assume the hypothesis is true for all sizes smaller than
Rewrite:
n, that is:
T(n) ≤ c * n * log n - (c * n - n)
T(k) ≤ c * k * log k for all k < n.
Choose c large enough (for example c ≥ 1) so that (c * n - n)
Now consider T(n):
≥ 0. Then,
T(n) = 2 * T(n/2) + n
T(n) ≤ c * n * log n
Using the inductive hypothesis on T(n/2):
This matches our inductive hypothesis.
T(n/2) ≤ c * (n/2) * log(n/2)
Step 7: Conclusion
Substitute this into the recurrence:
By induction, the solution to the recurrence
T(n) ≤ 2 * [c * (n/2) * log(n/2)] + n
T(n) = 2T(n/2) + n
Simplify:
is
T(n) ≤ c * n * log(n/2) + n
T(n) = O(n log n).
Since log(n/2) = log n - log 2 = log n - 1,
T(n) ≤ c * n * (log n - 1) + n
T(n) ≤ c * n * log n - c * n + n
 T(n) = aT(n/b) + f(n)
The Master Theorem a = number of subproblems
b = factor of input size division
f(n) = cost outside recursion

Theorem:
Theorem:
Let
Letaa 11and
andbb>>11be beconstants,
constants,letletf(n)
f(n)be beaafunction,
function,andand
Let
LetT(n)T(n)be
bedefined
definedon onnonnegative
nonnegativeintegers
integersbybythe
therecurrence
recurrence
T(n)
T(n)==aT(n/b)
aT(n/b)++f(n), f(n),where
wherewe wecancanreplace
replacen/bn/bby n/bor
byn/b orn/b.
n/b.
T(n)
T(n)can canbe
bebounded
boundedasymptotically
asymptoticallyin inthree
threecases:
cases:
1.
1. IfIf f(n)
f(n)==O(n
O(nlogbba–)) for
log a–
forsome
someconstant
constant>>0, 0,then
thenT(n)
T(n)==(n
(nlogbba).).
log a

2.
2. IfIf f(n)
f(n)==(n
(nlogbba),),then
log a
thenT(n)
T(n)==(n
(nlogbbalglgn).
log a
n).
3.
3. If f(n) = (n a+)) for
If f(n) = (n log
logbba+
forsome
someconstant
constant>>0, 0,
and
andif,if,for
forsome
someconstant
constantcc<<11and andall
allsufficiently
sufficientlylarge
largen, n,
we
wehave
havea·f(n/b)a·f(n/b) ccf(n),
f(n),then
thenT(n)T(n)==(f(n)).
(f(n)).
 The Master Theorem

• If T(n) = aT(n/b) + f(n) where a ≥ 1 & b > 1,then

 
 
 logb a
n  
f (n) O n logb a   

 
 logb a   0
T (n)  n lg n  
f (n)  n 
log b a

  c 1
 
 f (n)  
f (n)  n logb a  & 
 
 af (n / b)  cf (n) for large n
Interpretation of Master Theorem
• In each of the three cases, we are comparing f(n) with nlogba , the
solution to the recurrence is determined by the larger of the two
functions.

• In case 1, if the function nlogba is the larger, then the solution T(n)
= Θ(nlogba).

• In case 3, if the function f(n) is the larger, then the solution is T(n)
= (f(n)).

• In case 2, if the two functions are the same size, then the
solution is T(n) = Θ(nlogba lg n) = Θ(f(n) lg n).
 Using The Master Method:
Case 1
• T(n) = 9T(n/3) + n
– a=9, b=3, f(n) = n
– nlogb a = nlog3 9 = (n2) >> from log332
– Since f(n) = O(nlog3 9 - ) = O(n2-0.5) = O(n1.5)
– where =0.5
– case 1 applies:
  
T (n)  n log b a when f (n) O n log b a   
– Thus the solution is
• T(n) = (n2)
 Using The Master Method:
Case 2
• T(n) = T(2n/3) + 1
– a=1, b=3/2, f(n) = 1
– nlogba = nlog3/21 = n0 = 1
– Since f(n) = (nlogba) = (1)
– case 2 applies:
  
T (n)  n logb a lg n when f (n)  n logb a 

– Thus the solution is

• T(n) = (lg n)
Using The Master Method:
Case 3
• T(n) = 3T(n/4) + n lg n
– a=3, b=4, f(n) = n lg n
– nlogba = nlog43 = n0.793 = n0.8
– Since f(n) = W(nlog43+) = W(n0.8+0.2)= W(n)
– where   0.2, and for sufficiently large n,
• a . f(n/b) = 3(n/4) lg(n/4) < (3/4) n lg n for c = 3/4
– T
case 3 applies: ( n )   f ( n )  when f ( n )  n 
log b a 


– Thus the solution is

• T(n) = (n lg n)
 Case Study- Time Complexity Prediction for
Recursive File Backup System
• A software company implemented a recursive backup system that mirrors nested
folders and files. As directory depth increased, performance slowed. Engineers
needed to model and analyze the time taken using recurrence relations.
• Outcome- Derived recurrence helped estimate time cost as linear (O(n))
- Optimization shifted to I/O buffering instead of recursion changes
- Prevented overengineering and helped in decision-making for batch vs. recursive
backups
• Reference- CLRS (2009), Chapter 4: Recurrences
- Gries & Schneider (1993). A Logical Approach to Discrete Math
- Real-world analogy from Dropbox Engineering Blog: Efficient Backup Systems
 PRACTICE QUESTIONS

1.Solve the following recurrence relation using the iteration

method: T(n)=3T(n/2)+n
2. Solve the recurrence relation using the Master Theorem:
2T(n)=9T(n/3)+n2
 Summary of the Lecture

•Recurrence Relations express the runtime of recursive algorithms in

• terms of smaller input sizes, often capturing the structure of
divide-and-conquer algorithms.
•Solving Techniques include:
•Recursion Tree Method: Visualizing and summing costs at each level.
•Substitution Method: Using induction to prove a guessed bound.
•Master Theorem: Providing direct asymptotic bounds for specific recurrence
forms.
 Quiz
1. 2.

Ref: GATE 2025 Ref: GATE 2024

 References
9

• Mark Allen Weiss-Data Structures and Algorithm Analysis in C

• "Introduction to Algorithms" by Thomas H. Cormen, Charles E.
Leiserson, Ronald L. Rivest, and Clifford Stein, MIT Press.
• https://athena.nitc.ac.in/summerschool/Files/clrs.pdf
 0

Relevant learning resources

https://www.coursera.org/learn/analysis-of-algorithms
https://www.linkedin.com/advice/0/how-do-you-solve-recurre
nce-relations-master-theorem
 12

Thank You