1
UNIT-2
2
Recursion
• The process in which a function calls itself directly or indirectly
is called recursion and the corresponding function is called as
recursive function.
• Examples of such problems are Factorial, Towers of Hanoi
(TOH), Inorder/Preorder/Postorder Tree Traversals, DFS of
Graph, etc.
3
Example
int fact(int n)
{
if (n < = 1) // base case
return 1;
else
return n*fact(n-1);
}
4
Recurrence Relation
• A recurrence is an equation or inequality that describes a
function in terms of its values on smaller inputs.
• To solve a Recurrence Relation means to obtain a
function defined on the natural numbers that satisfy the
recurrence.
• For Example, the Worst Case Running Time T(n) of the
MERGE SORT Procedures is described by the
recurrence.
5
Recurrence Relation
• There are four methods for solving Recurrence:
1. Recursion Tree Method
2. Master Method
3. Substitution Method
4. Iteration Method
6
1. Recursion Tree Method
1. Recursion Tree Method is a pictorial representation of
an iteration method which is in the form of a tree where
at each level nodes are expanded.
2. In general, we consider the second term in recurrence
as root.
3. It is useful when the divide & Conquer algorithm is
used.
4. It is sometimes difficult to come up with a good guess.
In Recursion tree, each root and child represents the
cost of a single subproblem
7
Recursion Tree
Formulas:
𝑛 𝑖
𝑛 4) 𝑖=0 𝑥 =
1) 𝑖=0 1 = (n+1)
1
𝑛 𝑛(𝑛+1) x<1
2) 𝑖=0 𝑖 = 2 1−𝑥
3) 𝑛
𝑖=0 𝑖
2
=
𝑛(𝑛+1)(2𝑛+1)
x=1 n+1
6
𝑥 𝑛+1 −1
x>1
𝑥−1
8
Ques 1
𝑛
T(n) = 2T ( +17) +n
2
Ans: nlog2n
9
Ques 2
𝑛
T(n) = T ( ) +1
2
Ans: log2n
10
Ques 3
𝑛
T(n) = 2T ( ) +1
2
Ans: n
11
Ques 4
T(n) = T (n-1) +n
Ans: n2
12
Ques 5
𝑛
T(n) = 4T ( ) +n
3
Ans: n1.26
13
Ques 6
𝑛
T(n) = 16T ( ) +n3
4
Ans: n3
14
Ques 6
T(n) = 2T (√n) +logn m= logn
n=2m
n1/2=2m/2
Ans: mlogm= logn log logn T(2m)=2T(2m/2) + m
Take T(2m)= S(m)
S(m)= 2S(m/2) +m
15
Ques 7
𝑛 2𝑛
T(n) = T ( ) + T ( ) + n
3 3
Ans: nlog3/2n = nlog2n
16
Ques 8
9𝑛
T(n) = T ( ) + n
10
Ans: n
17
Ques 9
𝑛 𝑛 𝑛
T(n) = T ( ) +T ( ) +T ( ) +n
2 4 8
Ans: nlog23
18
Recursion Tree Method
19
Recursion Tree Method
20
2. Master Theorem
If a>= 1and b>1 be constants, let f(n) be a function and T(n) be defined on the
non-negative integers by the recurrence
T(n) = aT(n/b) + f(n)
where, T(n) has the following asymptotic bounds:
1. If f(n) = O (nlogba-ϵ), then T(n) = Θ(nlogb a)
2. If f(n) = Θ (n logba), then T(n) = Θ(nlogba log n)
𝑛
3. If f(n) = Ω (n logba+ϵ), and if ϵ > 0 is a constant and if a f(𝑏 ) <= c f(n)
for some constant c< 1, then T(n) = Θ(f(n))
21
Ques 1
𝑛 a=2, b=2, f(n)=n
T(n) = 2T ( ) +n
2
Find nlogba
Ans: nlog2n = nlog22
=n
Case2:
Θ(nlogba log n)
=Θ(nlog n)
22
Ques 2
𝑛
a=4, b=2, f(n)=n
T(n) = 4T ( ) +n
2
Find nlogba
Ans: n2 = nlog24
=n2 =n2-ϵ
Case1:
Θ(nlogba)
=Θ(n2)
23
Ques 3
a=16, b=4, f(n)=n3
𝑛
T(n) = 16T ( ) +n3 Find nlogba
4
= nlog416
Ans: n3 =n2 =n2+ϵ
Case3:
𝑛 𝑛 3 1
a f( ) = 16 = n3
𝑏 4 4
c<1
Θ(f(n))= Θ(n3)
24
Ques 4
𝑛
T(n) = 49T ( ) +n
7
Ans: n2
25
Ques 5
𝑛
T(n) = 2T ( ) +logn
2
Can’t implement Master’s Theorem
26
Master Theorem
27
3. Iteration Method
The iteration method is a "brute force" method of solving a
recurrence relation.
The general idea is to iteratively substitute the value of the
recurrent part of the equation until a pattern (usually a
summation) is noticed, at which point the summation can
be used to evaluate the recurrence.
28
Example
29
Example
30
Example
31
Example
32
Example (same as above)
33
Example
34
Question 1
35
Solution 1
36
Solution 1
37
Solution 1
38
Solution 1
39
Question 2
Θ(lg(n))
40
Question 3
T(n) = 2T(n/2) + n
Θ(nlg(n))
41
4. Substitution Method
• The Substitution Method Consists of two main steps:
1. Guess the Solution.
2. Use the mathematical induction to find the boundary
condition and shows that the guess is correct.
42
Example
Recurrence relation: T(1) = 1 and T(n) = 2T(n/2) + n for n > 1
Step 1: We guess that the solution is T(n) = O(nlogn)
Step 2: Let's say c is a constant hence we need to prove that :
T(n) ≤ cnlogn for all n ≥ 1
Step 3: Using the above statement we can assume that :
T(n) ≤ 2c n/2 log(n/2) + n
T(n) = cn log(n) - cn log(2) + n
T(n) = cn log(n) - cn + n
T(n) = cn log(n) + n(1 - c)
hence T(n) ≤ cnlog(n) for all c ≥ 1
Step 4: Now we need to put the values into the recurrence formula,
T(2) = 2T(1) + 2 = 4 and T(3) = 2T(1) + 3 = 5,
Now choose a c that perfectly fits our inequality obtained above in step 3, let say c = 2 :
4 ≤ 4log(2) and 5 ≤ 6log(3) perfectly satisfy the condition,
Hence we can conclude that T(n) ≤ 2n log n for all n ≥ 2, therefore T(n) = O(n log n)
43
Question 1
Solve the equation by Substitution Method.
44
• Let say its O(log n)
• We have to show that for some constant c
• T (n) ≤c logn.
45
Question 2
T(n)=4T(n/2)+n
