SOFE3770U: Data Structure
Week 4: Solving Recurrences
Dr. Anwar Abdalbari
Based on lecture notes by Masoud Makrehchi 2024
Agenda
Solving Recurrences
- Substitution method
- Recursion-tree method
- Master method
Maximum-subarray problem
Analyzing the maximum-subarray problem
2
Recurrence
A recurrence relation is a formula that shows how the
time or space complexity of an algorithm depends on
the size of its input.
It is often used to study and predict the performance
of algorithms, especially those that use divide-and-
conquer, dynamic programming, or recursion.
3
Recurrence
A recurrence function typically expresses the time or space
complexity T(n) in terms of one or more smaller subproblems of
the same kind, usually with smaller input sizes. The general
form of a recurrence function is:
T(n) = T(g(n)) +f(n)
Here, T(n) represents the complexity of the algorithm for an
input of size n, f(n) represents the work done in solving the
current problem of size n, and T(g(n)) represents the
complexity of solving one or more subproblems of size g(n),
where g(n) is typically smaller than n.
4
Recurrence
• Solving recurrence functions involves finding
a closed-form solution, which is an explicit
expression for T(n) in terms of n, without any
recursive terms.
• This closed-form solution helps in
understanding the overall complexity of the
algorithm and making predictions about its
behavior for large input sizes.
5
Recurrence
• Common techniques for solving recurrence
relations include substitution, recurrence tree, and
the master theorem, depending on the specific
form of the recurrence.
• Analyzing and solving recurrence functions is a
fundamental skill in algorithm design and analysis
because it allows you to estimate the time and
space efficiency of algorithms, which is crucial for
making informed choices in algorithm selection and
optimization.
6
Solving Recurrences
1. Substitution method
2. Recursion-tree method
3. Master method
7
1. Substitution method
It has the following two steps:
1. Guess the form of the solution.
2. Use mathematical induction to find the
constants and show that the solution works.
3. Solve for any constants in the solution
This method is powerful, but we must be able to
guess the form of the answer in order to apply it.
Applicable for upper or lower bounds on a
recurrence
8
Substitution method: Example 1
For the code shown on the right, the recurrence
relation is shown below:
9
Substitution method: Example 1 Cont’d
Step 1: Write recurrence Step 3: Stop at base case
𝑇 𝑛 =𝑇 𝑛−1 +1 Choose 𝑘 = 𝑛:
𝑇 𝑛 =𝑇 𝑛−𝑛 +𝑛
Step 2: Apply substitution =𝑇 0 +𝑛
repeatedly Step 4: Apply base condition
First substitution: 𝑇 0 =1
𝑇 𝑛 = 𝑇 𝑛−2 +1 +1 So,
=𝑇 𝑛−2 +2 𝑇 𝑛 =1+𝑛
Final solution by substitution
Second substitution: method:
𝑇 𝑛 =𝑇 𝑛−3 +3 𝑇 𝑛 =𝑛+1
General form:
𝑇 𝑛 =𝑇 𝑛−𝑘 +𝑘
10
Substitution method: Example 2
Recurrence Relation
11
Substitution method: Example 2
Step 1: Expand once Step 4: General pattern
𝑛 After 𝑘 expansions:
𝑇 𝑛 = 2𝑇 +𝑛 𝑛
2 𝑇 𝑛 = 2𝑘 𝑇 +𝑘⋅𝑛
2𝑘
Step 2: Expand 𝑇 𝑛/2 Step 5: Stop at base case
𝑛 𝑛 𝑛 Base case when
𝑇 = 2𝑇 +
2 4 2 𝑛
= 1 ⟹ 2𝑘 = 𝑛 ⟹ 𝑘 = 𝑙𝑜𝑔2 𝑛.
Substitute: 2𝑘
𝑛 𝑛
𝑇 𝑛 = 2(2𝑇 + )+𝑛
4 2 So:
𝑛 𝑇 𝑛 = 2𝑙𝑜𝑔2 𝑛 ⋅ 𝑇 1 + 𝑛 ⋅ 𝑙𝑜𝑔2 𝑛
𝑇 𝑛 = 4𝑇 + 2𝑛
4
Step 6: Simplify
Step 3: Expand again
𝑛 𝑛 𝑛 Since 2𝑙𝑜𝑔2 𝑛 = 𝑛 𝑎𝑛𝑑 𝑇 1 = Θ 1 :
𝑇 = 2𝑇 +
4 8 4 𝑇 𝑛 = 𝑛 ⋅ Θ 1 + 𝑛 log 𝑛
Substitute: 𝑇 𝑛 = Θ 𝑛 log 𝑛
𝑛 𝑛
𝑇 𝑛 = 4(2𝑇 + ) + 2𝑛
8 4
𝑛
𝑇 𝑛 = 8𝑇 + 3𝑛
8
12
Substitution method: Example 3
1. We guess:
2. The substitution method requires us to prove that :
It holds for c>1.
13
Recursion-tree method
• A straightforward way to devise a good guess
(can be used by Substitution method)
• 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, and then we
sum all the per-level costs to determine the total
cost of all levels of the recursion.
14
Recursion-tree method
• Making a good guess is sometimes difficult with the substitution
method.
• Recursion Tree Method can be used to devise a good guess.
• Recursion Trees show successive expansions of recurrences
using trees.
• Recursion Trees model the costs (time) of a recursive
execution of an algorithm that is composed of two part:
• cost of non-recursive part.
• cost of recursive call on smaller input size.
• A Tree node represents the cost of a sub-problem (recursive
function invocation).
• To determine the total cost of the Recursion Tree, evaluate:
• Cost of individual node at depth “i”
• Sum up the cost of all nodes at depth “i”
• Sum up all per-level costs of the Recursion Tree.
Recursion-tree: Depth, Level, Width
Level = Depth + 1
16
Recursion-tree: Example 1
Solve the following recurrence using the Recurrence Tree Method.
Assumption: We assume that 𝑛 is exact power of 2.
Recursion-tree: Example 1 Cont.
𝑛
𝑇(𝑛) = 2𝑇 +n
2
𝑛 𝑛 𝑛
𝑇 = 2𝑇 2 +
2 2 2
𝑛 𝑛 𝑛
𝑇 = 2𝑇 +
22 23 22
𝑛 𝑛 𝑛
𝑇 = 2𝑇 +
2𝑘−1 2𝑘 2𝑘−1
𝑛
𝑇 =𝑇 1
2𝑘
𝑛 = 2k ⇒ k = log n
𝐿𝑐 = 2𝑘 ⇒ 2log 𝑛 ⇒ 𝑛
Total cost = Cost of Leaf Nodes
+ Cost of Internal Nodes
Total Cost = (cost of leaf node x total leaf nodes) + (sum of costs at each level of internal nodes)
Total Cost = Lc + Ic
Recursion-tree: Example 1 Cont.
To Calculate 𝐼𝑐
𝐼𝑐 = 𝑘. 𝑛
𝐼𝑐 = 𝑛 𝑙𝑜𝑔 𝑛
Total cost: 𝐿𝑐 + 𝐼𝑐 ⇒ 𝑛 + n log 𝑛
𝑇 𝑛 = 𝑂(𝑛 log 𝑛)
Recursion-tree method: Example
20
Recursion-tree method: Example
(Cont.)
21