NATIONAL UNIVERSITY OF MODERN LANGUAGES
RAWALPINDI
DEPARTMENT OF SOFTWARE ENGINEERING
BS-SE-5
ASSIGNMENT#02
SUBJECT: Analysis of Algo..
Submitted by:
Kaynat Ellahi
Solving Recurrence Relations: Methods
In algorithm analysis, recurrence relations describe the running time of recursive
algorithms. Different methods exist to solve them and determine their asymptotic behavior.
Here, we discuss three popular methods: Substitution, Iteration, and Master Theorem
1. Substitution Method
Explanation:
The Substitution Method involves guessing the solution of a recurrence relation and then
using mathematical induction to prove it. It is often used when other methods are difficult
or when an exact closed form is hard to find.
Step-by-Step Procedure:
1. Guess the solution based on the recurrence pattern.
2. Use mathematical induction to prove the guessed solution.
3. Adjust the constants in your guess if necessary to satisfy the base case and
recurrence.
Example:
Solve the recurrence:
𝑇(𝑛) = 2𝑇(𝑛/2) + 𝑛
Step 1: Guess the solution
We guess 𝑇(𝑛) = 𝑂(𝑛log 𝑛).
Step 2: Use induction
Assume 𝑇(𝑘) ≤ 𝑐 ⋅ 𝑘log 𝑘for all 𝑘 < 𝑛. Then,
𝑛 𝑛
𝑇(𝑛) = 2𝑇(𝑛/2) + 𝑛 ≤ 2 ⋅ 𝑐 ⋅ log + 𝑛 = 𝑐𝑛log(𝑛/2) + 𝑛 = 𝑐𝑛(log 𝑛 − 1) + 𝑛
2 2
= 𝑐𝑛log 𝑛 − 𝑐𝑛 + 𝑛 = 𝑐𝑛log 𝑛 − (𝑐 − 1)𝑛
For 𝑐 ≥ 1, this satisfies the recurrence.
Step 3: Conclude
𝑇(𝑛) = Θ(𝑛log 𝑛)
2. Iteration Method
Explanation:
The Iteration Method involves repeatedly expanding the recurrence until a pattern emerges.
Then, the sum of all terms is simplified to find the asymptotic complexity.
Step-by-Step Procedure:
1. Expand the recurrence for a few levels.
2. Look for a pattern in the terms.
3. Sum the series to obtain the final closed form.
4. Simplify to get asymptotic behavior.
Example:
Solve the recurrence:
𝑇(𝑛) = 3𝑇(𝑛/3) + 𝑛
Step 1: Expand the recurrence
𝑇(𝑛) = 3𝑇(𝑛/3) + 𝑛
= 3(3𝑇(𝑛/9) + 𝑛/3) + 𝑛 = 9𝑇(𝑛/9) + 𝑛 + 𝑛 = 9𝑇(𝑛/9) + 2𝑛
= 27𝑇(𝑛/27) + 3𝑛(after 3 expansions)
Step 2: Identify the pattern
After 𝑘expansions:
𝑇(𝑛) = 3𝑘 𝑇(𝑛/3𝑘 ) + 𝑘𝑛
Step 3: Base case
Let 𝑛/3𝑘 = 1 ⟹ 𝑘 = log3 𝑛.
𝑇(𝑛) = 𝑛𝑇(1) + 𝑛log3 𝑛
Step 4: Conclude
𝑇(𝑛) = Θ(𝑛log 𝑛)
3. Master Theorem
Explanation:
The Master Theorem provides a direct way to determine the asymptotic behavior of divide-
and-conquer recurrences of the form:
𝑇(𝑛) = 𝑎𝑇(𝑛/𝑏) + 𝑓(𝑛)
where 𝑎 ≥ 1, 𝑏 > 1, and 𝑓(𝑛)is an asymptotically positive function.
Step-by-Step Procedure:
1. Identify 𝑎, 𝑏, and 𝑓(𝑛)in the recurrence.
2. Compute 𝑛log𝑏 𝑎 .
3. Compare 𝑓(𝑛)with 𝑛log𝑏 𝑎 :
o Case 1: If 𝑓(𝑛) = 𝑂(𝑛log𝑏 𝑎−𝜖 )for some 𝜖 > 0, then 𝑇(𝑛) = Θ(𝑛log𝑏 𝑎 )
o Case 2: If 𝑓(𝑛) = Θ(𝑛log𝑏 𝑎 ), then 𝑇(𝑛) = Θ(𝑛log𝑏 𝑎 log 𝑛)
o Case 3: If 𝑓(𝑛) = Ω(𝑛log𝑏 𝑎+𝜖 )and the regularity condition holds, 𝑇(𝑛) =
Θ(𝑓(𝑛))
Example:
Solve the recurrence:
𝑇(𝑛) = 4𝑇(𝑛/2) + 𝑛2
Step 1: Identify constants
𝑎 = 4, 𝑏 = 2, 𝑓(𝑛) = 𝑛2
Step 2: Compute 𝑛log𝑏 𝑎
log2 4 = 2 ⟹ 𝑛log2 4 = 𝑛2
Step 3: Compare 𝑓(𝑛)with 𝑛log𝑏 𝑎
Here, 𝑓(𝑛) = 𝑛2 = Θ(𝑛log2 4 ), so this is Case 2.
Step 4: Conclude
𝑇(𝑛) = Θ(𝑛2 log 𝑛)
References:
• Cormen, T., Leiserson, C., Rivest, R., & Stein, C. (2009). Introduction to Algorithms.
MIT Press.
• Goodrich, M., Tamassia, R., & Goldwasser, M. (2014). Data Structures and Algorithms
in Java.