0% found this document useful (0 votes)
4 views14 pagesChapter-1 Module 2.pptm
The document outlines a systematic approach to analyze the time efficiency of recursive algorithms, detailing steps such as identifying input size, basic operations, and establishing recurrence relations. It includes examples like the computation of factorials, the Tower of Hanoi problem, and Fibonacci numbers, illustrating how to set up and solve recurrence relations. Additionally, it discusses methods such as backward substitution and the RHOAF method for analyzing recursive algorithms.
Uploaded by
haniyamody02Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF or read online on Scribd
0% found this document useful (0 votes)
4 views14 pagesChapter-1 Module 2.pptm
The document outlines a systematic approach to analyze the time efficiency of recursive algorithms, detailing steps such as identifying input size, basic operations, and establishing recurrence relations. It includes examples like the computation of factorials, the Tower of Hanoi problem, and Fibonacci numbers, illustrating how to set up and solve recurrence relations. Additionally, it discusses methods such as backward substitution and the RHOAF method for analyzing recursive algorithms.
Uploaded by
haniyamody02Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF or read online on Scribd
Design and Analysis of
Algorithms
Reference : Introduction to Design and
Analysis of Algorithms
3" Edition
by
Anany Levitin
VI BCA 2024 Chapter 1 Module 2 General Plan for Analyzing the Time Efficiency of
Recursive Algorithms :
1. Decide on a parameter (or parameters) indicating an input's size.
2. Identify the algorithm’s basic operation.
3. Check whether the number of times the basic operation is executed can vary
on different inputs of the same size; if it can, the worst-case, average-case,
and
best-case efficiencies must be investigated separately.
4. Set up a recurrence relation, with an appropriate initial condition, for the
number of times the basic operation is executed.
5. Solve the recurrence or, at least, ascertain the order of growth of its solution. Example :
ALGORITHM F(n)
//Computes n! recursively
//\nput: A nonnegative
integer n
//Output: The value of n!
ifn=0
return 1
else
return F (n-1)#n
The basic operation of the algorithm is multiplication, whose
number of executions we denote M(n). Analysis :
The number of multiplications M(n) needed to compute it must
satisfy the equality
M(n)=M(n-1) + 1 forn>0
Tocompute F(n-1) TomultiplyF(n-1) by n
The recurrence relation and initial condition for the algorithm's
number of multiplications M(n) :
M(n) = M(n - 1) +1 forn>0,
M(0) = 0 Backward
substitution :
From the several techniques available for solving recurrence
relations, we use what can be called the method of backward
substitutions.
M(n) =M(n-1) +1
=M(n-2)+1+1 M(n) =M(n-1)+1
=M(n-2)+ 2
=M(n-3)+14+2
|
=M(n-(n)) +n
= M(0) +n=
= 0 +n=n Tower of Hanoi
In puzaas, we have n disks of different sizes that can slide
onto any of three pegs. Initially, all the disks are on the first peg in
order of size, the largest on the bottom and the smallest on top.
The goal is to move all the disks to the third peg, using the second
one as an auxiliary, if necessary. We can move only one disk ata
time, and it is forbidden to place a larger disk on top of a smaller
one. Tower of Hanoi
cle MeAPrber of moves M(n) depends on n only, and we get the following recurrence
equation for it:
M(n) = M(n- 1) +1#M(n-1) forn>1
With the obvious initial condition M(1) = 1, we have the following recurrence
M(n) = 2M(n- 1) +1 forn>1,
M(1) =1
We solve this recurrence by the same method of backward substitutions:
M(n) = 2M(n~ 1) +1 sub, M(n~ 1) =2M(n-2)+#1
= 2[2M(n- 2)+ 1} 1=2'M(n-2)+2+1 sub. M(n-2)=2M(n-3)+1
=2(2M(n- 3) + 1]4 241
=2'M(n-3)+2°4+2+1
=2'M(n- 4) + 2° + 2'+2 +1, and generally, after i substitutions, we get
M(n) =2M(n~i) #24274. ..4241=2M(n- paz
Since the initial condition is specified for n = 1, which is achieved fori =n ~ 1, we get the
following formula for the solution to recurrence :
M(n) = 2’ M(n - (n= 1)) +2"
=2''M(1) +2" - 1=2" 42" -452'-1 Recursive Version of Binary
Digits :
ALGORITHM BinRec(n)
//nput: A positive decimal integer n
//Output: The number of binary digits in n's binary
representation
ifn=1
return 1
else
return BinRec(n/2) + 1
Let us set up a recurrence and an initial condition for the number of
additions
A(n) made by the algorithm.
The number of additions made in computing BinRec(n/2) is A(n/2), plus
one more addition is made by the algorithm to increase the returned
value by 1. This leads to the recurrence
A(n) = A(n/2) +1 forn>1. Recurrence Relation &
i : A(n) = A(n/2) +1 forn > 1.
Solution.;.,. recursive calls end when n is equal to 1 and there are no additions
made then, the initial condition is
A(1) =0
Hence the recurrence relation is :
A(2') = A(2""') +1 for k > 0,
A(2°) = 0.
Now backward substitutions encounter no problems:
A(2') = A(2"') +1 substitute A(2"') = A(2"*) +1
= [A(2"*) + 1] 1= a) + 2 substitute A(2'%) = A(2"*) +1
= [A(2"*) + 1]+ 2 =A(2*) +3...
FAQ*)+1 = AQ") +k,
Thus, we end up with
A(2’') = A(1) +k=k,
or, after returning to the original variable n = 2° and hence k = log: n,
A(n) = loge n € 6 (log n). Computing n" Fibonacci
number :
Fibonacci Numbers :
0, 1,1, 2, 3, 5, 8, 13, 21, 34...
It can be defined by the simple recurrence
F (n) =F (n-1)+F(n-2)forn>1
and two initial conditions
F (0) = 0, F(1) =1
If we try to apply the method of backward
substitutions to solve the above recurrence, we will fail
to get an easily
discernible pattern. Computing n” Fibonacci
RHOAF method for solving recurrence relations useful
for analysis of recursive algorithms.
Instead, we can apply the theorem that describes
solutions to a homogeneous second-order linear
recurrence with constant co-efficients
ax(n) + bx(n - 1) + cx(n - 2) =0
where a, b, and c are some fixed real numbers (a != 0)
called the coefficients of the recurrence.
x(n) is the generic term of an unknown sequence to be
found.
ar +br+c=0 & Quadratic equation is called the
characteristic equation for recurrence equation Algorithm :
ALGORITHM F(n)
//Computes the nth Fibonacci number recursively by using its
definition
//\nput: A nonnegative integer n
//Output: The nth Fibonacci number
ifns1
return n
else
return F (n - 1) +F (n- 2)
The basic operation of the algorithm is Addition, whose number of
executions we denote A(n). Analysis :
We get the following recurrence for A(n):
A(n) = A(n- 1) +A(n-2) +1 forn>1,
A(0) = 0,
A(1) =0
Now A(n) = A(n - 1) + A(n - 2) + 1 can be writeen as
A(n) - A(n - 1) -A(n - 2) =1
Since this equation is equal to 1, it is inhomogeneous
So, we write it as :
A(n) - A(n - 1) -A(n - 2)-1=0
[A(n) + 1] - [A(n - 1) + 1] - [A(n - 2) + 1] = 0
and substituting B(n) = A(n) + 1, we write it as :
B(n) - B(n- 1) - B(n-2)=0, War+br+c=0
B(O) = 1,B(1)=1
A(n) = B(n) - 1 =F (n+1)-1= 1/15 (p™ - g™")-1 Example :
ALGORITHM MatAdd(A,B,C,n)
for (i = 0; i