Recurrence Relations
4.4 and 4.5 from
Cormen, T.H., Leiserson, C.E., Rivest, R. L., Stein C. Introduction to Algorithms, 4th
edition,
Prentice Hall of India, 2022.
Recursive Algorithms
• A recursive algorithm is one in which objects are
defined in terms of other objects of the same type.
• Advantages:
– Simplicity of code
– Easy to understand
• Disadvantages
– Memory
– Speed
– Possibly redundant work
Recursive Algorithms: Analysis
• We have already discussed how to analyze the
running time of (iterative) algorithms
• To analyze recursive algorithms, we require
more sophisticated techniques
• Specifically, we study how to define & solve
recurrence relations
Recurrence Relation
A recurrence relation is an equation which represents a sequence based on some rule.
It helps in finding the subsequent term (next term) dependent upon the preceding
term (previous term). If we know the previous term in a given series, then we can
easily determine the next term. Since a standard pattern is developed now, we can
find the set of new terms.
Let us assume xn is the nth term of the series. Then the recurrence relation is shown in the form of;
xn = f(xn) + 1 ; n>0
We can also define a recurrence relation as an expression that represents each element of a series as a function of the preceding ones.
x = f(n,x ) ; n>0
n n-1
To write the recurrence relation of first-order, say order k, the above formula can be represented as;
xn = f(n, xn-1 , xn-2 , ……, xn-k) ; n-k>0
Factorial Representation
We can define the factorial by using the concept of recurrence relation, such as;
n!=n(n-1)! ; n>0
When n = 0, 0! = 1 is the initial condition.
To find the further values we have to expand the factorial notation, where the succeeding term is
dependent on the preceding one.
Fibonacci Numbers
In Fibonacci numbers or series, the succeeding terms are dependent on the last two preceding terms.
Therefore, this series is the best example of recurrence. As we know from the definition of the
Fibonacci sequence,
Fn = Fn-1 + Fn-2
Now, if we take the initial values; F0 = 0 and F1 = 1
So, F2 = F1 + F0 = 0 + 1 = 1
In the same way, we can find the next succeeding terms, such as;
F3 = F 2 + F1
F4 = F 3 + F 2
And so on.
Thus, the Fibonacci series is given by; 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, …∞
Motivating Examples: Factorial
• Recall the factorial function: 1 if n= 1
n! =
n.(n-1) if n > 1
• Consider the following (recursive) algorithm for computing n!
Factorial
Input: n∈N
Output: n!
1. If (n=1) or (n=0)
2. Then Return 1
3. Else Return n × Factorial(n-1)
4. Endif
5. End
Factorial: Analysis
How many multiplications M(x) does factorial perform?
• When n=1 we don’t perform any
• Otherwise, we perform one…
• … plus how ever many multiplications we perform in the recursive call
Factorial(n-1)
• The number of multiplications can be expressed as a formula (similar to the
definition of n!
M(0) = 0
M(n) = 1 + M(n-1)
• This relation is known as a recurrence relation
Recurrence Relations
• A recurrence relation is an equation or an inequality that
characterizes a function by its values on smaller inputs.
They are also called Difference Equations.
Eg: T(n) = 1 if n = 1
T(n) = 2T(n/2) + n if n > 1
• A recurrence relation for a sequence {an} is an equation
that expresses an in terms of one or more of the previous
terms in the sequence: a0, a1, a2, …, an-1 for all integers
n≥n0 where n0 is a nonnegative integer.
• A sequence is called a solution of a recurrence if its
terms satisfy the recurrence relation.
Recurrence Examples
Solution Methods for Recurrence Relations:
1. Substitution Method.
2. Recursion-tree Method.
3. Master Method.
Recursion tree method is used to solve recurrence relations. Generally, these recurrence relations follow the divide and
conquer approach to solve a problem, for example T(n) = T(n-1) + T(n-2) + k, is a recurrence relation as problem size 'n'
is dividing into problems of size n-1 and n-2. can be solved with recursion tree method.
•When a problem is divided into smaller subproblems, there is also some time needed to combine the
solutions to those subproblems to form the answer to the original problem.
• For example, the recurrence relation for Merge sort is T(N) = 2 * T(N/2) + O(N). This additional O(N) is
the time required to combine the solutions of two subproblems of size T(N/2) which is true at the
implementation level as well. We merge two sorted arrays to form a new sorted array in linear time in
the merge step of Merge sort.
• For example, the recurrence relation for Binary search is T(N) = T(N/2) + 1, we know that in Binary
search the search space is reduced to half in each iteration. As soon as we find the result, we return
from the function. This is a constant time operation, this is the reason why +1 is added in the recurrence
relation.
In the recursion tree method, the time required to solve a subproblem is referred to as the cost
of the subproblem. So if you find "cost" word associated with the recursion tree then it
means nothing but the time required to solve a subproblem
To solve a recurrence relation using the recursion tree method, a few steps must be followed.
They are,
[Link] the recursion tree for the given recurrence relation.
[Link] the height of the recursion tree formed.
[Link] the cost(time required to solve all the subproblems at a level) at each level.
[Link] the total number of nodes at the last level and the cost of last level.
[Link] up the cost of all the levels in the recursion tree.
T(n) = 2T(n/2) + K, T(1)=1
Solution:
The given recurrence relation shows the following properties,
•A problem size n is divided into two sub-problems each of size n/2. The cost of combining the
solutions to these sub-problems is K.
•Each problem size of n/2 is divided into two sub-problems each of size n/4 and so on.
•At the last level, the sub-problem size will be reduced to 1. In other words, we finally hit the base
case.
Step. 2 Calculate the Height of the Tree
•Since we know that when we continuously divide a number by 2, there comes a time when this number
is reduced to 1. Same as with the problem size n, suppose after K divisions by 2, n becomes equal to 1,
which implies, (n / 2^k) = 1
•Here n / 2^k is the problem size at the last level and it is always equal to 1.
•Now we can easily calculate the value of k from the above expression by taking log() to both sides. Below is a
more clear derivation,
•n / 2^k = 1
• n = 2^k
• log(n) = log(2^k)
• log(n) = k * log(2)
• k = log(n) / log(2)
• k = log(n) base 2
So the height of the tree is log(n) base 2.
Step. 3 Calculate the cost at each level
•Cost at Level-0 = K, two sub-problems are merged.
•Cost at Level-1 = K + K = 2*K, two sub-problems are merged two times.
•Cost at Level-2 = K + K + K + K = 4*K, two sub-problems are merged four times. and
so on....
Step. 4 Calculate the number of nodes at each level
From the recursion tree, we can deduce this
•Level-0 have 1 (2^0) node
•Level-1 have 2 (2^1) nodes
•Level-2 have 4 (2^2) nodes
•Level-3 have 8 (2^3) nodes
So the level log(n) should have 2^(log(n)) nodes i.e. n
nodes.
Step. 5 Sum up the cost of all the levels
•The total cost can be written as,
• Total Cost = Cost of all levels except last level + Cost of last level
• Total Cost = Cost for level-0 + Cost for level-1 + Cost for level-2 + .... + Cost for level-log(n) +
Cost for last level
•The cost of the last level is calculated separately because it is the base case and no merging is done
at the last level so, the cost to solve a single problem at this level is some constant value. Let's take it
as O(1).
•Let's put the values into the formulae,
• T(n) = K + 2*K + 4*K + .... + log(n)` times + `O(1) * n
• T(n) = K(1 + 2 + 4 + .... + log(n) times)` + `O(n)
• T(n) = K(2^0 + 2^1 + 2^2 + ....+ log(n) times + O(n)
•If you closely take a look to the above expression, it forms a Geometric progression (a, ar, ar^2, ar^3
...... infinite time). The sum of GP is given by S(N) = a / (r - 1). Here a is the first term and r is
the common ratio.
•In the GP formed above, a = 1 and r = 2, after solving this we get,
• T(n) = K * (1 / (2 - 1))` + `O(n)
• T(n) = K + O(n)
Thus, T(n) = O(n)
Recursion-tree Method
The Recursion Tree Method is a way of solving recurrence relations. In this method, a
recurrence relation is converted into recursive trees. Each node represents the cost incurred
at various levels of recursion. To find the total cost, costs of all levels are summed up.
Steps to solve recurrence relation using recursion tree method:
[Link] a recursive tree for given recurrence relation
[Link] the cost at each level and count the total no of levels in the recursion tree.
[Link] the total number of nodes in the last level and calculate the cost of the last level
[Link] up the cost of all the levels in the recursive tree
T(n) = 2T(n/2) + c
Step 1: Draw a recursion tree
Step 2: Calculate the work done or cost at each level and count total no of levels in recursion tree
Step 2 (contd..):
Count the total number of levels –
Choose the longest path from root node to leaf node
n/20 -→ n/21 -→ n/22 -→ ……… -→ n/2k
Size of problem at last level = n/2k
At last level size of problem becomes 1
n/2k = 1
2k = n
k = log2(n)
Total no of levels in recursive tree = k +1 = log2(n) + 1
Step 3: Count total number of nodes in the last level and calculate cost of last
level
No. of nodes at level 0 = 20 = 1
No. of nodes at level 1 = 21 = 2
………………………………………………………
No. of nodes at level log2(n) = 2log2(n) = nlog2(2) = n
Cost of sub problems at level log2(n) (last level) = n x T(1) = n x 1 = n
Step 4: Sum up the cost all the levels in recursive tree
T(n) = c + 2c + 4c + —- + (no. of levels-1) times + last level cost
= c + 2c + 4c + —- + log2(n) times + Θ(n)
= c(1 + 2 + 4 + —- + log2(n) times) + Θ(n)
1 + 2 + 4 + —– + log2(n) times –> 20 + 21 + 22 + —– + log2(n) times –>
Geometric Progression(G.P.)
= c(1) + Θ(n)
Thus, T(n) = Θ(n)
T(n) = T(n/10) + T(9n/10) + n
Step 2: Calculate the work done or cost at each level and count total no of levels in recursion tree
Count the total number of levels –
Choose the longest path from root node to leaf node
(9/10)0n –> (9/10)1n –> (9/10)2n –> ……… –> (9/10)kn
Size of problem at last level = (9/10)kn
At last level size of problem becomes 1
(9/10)kn = 1
k
(9/10) = 1/n
k = log10/9(n)
Total no of levels in recursive tree = k +1 = log10/9(n) + 1
Step 3: Count total number of nodes in the last level and calculate cost of last level
No. of nodes at level 0 = 2 = 1
0
No. of nodes at level 1 = 2 = 21
………………………………………………………
No. of nodes at level log10/9(n) = 2log (n) = nlog10/9(2)
10/9
Cost of sub problems at level log2(n) (last level) = nlog 10/9(2)
x T(1) = nlog
10/9(2)
x1=
nlog (2)
10/9
Step 4: Sum up the cost all the levels in recursive tree
T(n) = n + n + n + —- + (no. of levels – 1) times + last level cost
= n + n + n + —- + log10/9(n) times + Θ(nlog10/9(2))
= nlog10/9(n) + Θ(nlog10/9(2))
Thus, T(n) = Θ(nlog10/9(n))
Master Theorem
Master Theorem
Let a ≥ 1 and b > 1 be constants, and let f(n) be a nonnegative function
defined on exact powers of b. Define T(n) on exact powers of b by the
recurrence
T(n) = Θ(1) if n = 1,
T(n) = aT(n/b) + f(n) if n = bi, i is a +ve integer.
Then T(n) can be bounded asymptotically for exact powers of b as follows.
1. If f(n) = O(nlogba–ε) for some constant ε > 0, then T(n) = Θ(nlogba).
2. If f(n) = Θ(nlogba), then T(n) = Θ(nlogbalg n).
3. If f(n) = Ω(nlogba+ε) for some constant ε > 0, and af(n/b) ≤ c f(n) for some
constant c < 1 and large n, then T(n) = Θ(f(n)).
CASE 1
CASE 2
CASE 3