[Music] in our previous lectures we learned how to solve the recurrence relation of time and how to solve the recurence relation of return value using substitution method now in this lecture we will learn how to solve recurence relation of multiplications using substitution method so let's get started with this lecture and let's see the topics the first topic is writing the recurence relation of multiplications we will learn how to write the recurence relation of multiplications first and then we will proceed and solve the recurence relation using substitution method so first we will learn to write the
recurence relation of multiplications and then we will solve this recurence relation using substitution method so let's start with the first topic writing the reference relation of multiplications what do we mean by writing the recurence relation of multiplications here the number of operations is the multiplications we are interested in knowing the number of multiplications of this algorithm we want to know how many multiplications are needed in order to compute factorial of N and for this we want to write the recurence relation we know what is recurence Rel relation this is the algorithm to compute fact of
n or factorial of n if n is equal to 1 then 1 will be returned from the function otherwise n * fact of n minus 1 will be returned from this function now we are interested in writing the reference relation of the number of multiplications required to compute factorial of n how do we write one we know the meaning of the recurence Rel ation from our previous lectures recall that a recurence relation is a mathematical expression which is used to describe the cost of the overall problem in terms of the cost of solving the smaller
sub problems here the cost is the number of multiplications as we want to write the recurrence relation of multiplications the cost must be the number of multiplications so let us suppose MN represents the cost in terms of multiplications of fact of n this means MN represents the number of multiplications required to compute factorial of n so this is the cost of the overall problem we have we want to know the number of multiplications required to compute factorial of N and we are representing the number of multiplications required to compute factorial of n by MN now
we want to represent MN in terms of the cost of solving the smaller sub problems we know the cost is the number of multiplications so now let's represent MN in terms of the number of multiplications required to compute these sub problems this is the base case and this is the recursive case of this algorithm these are the smaller sub problems and now we want to know the number of multiplications required to compute these smaller sub problems let's see how many multiplications are needed to compute the base case here we have if n is 1 then
return one in this case we can observe that there are no multiplications involved we are just checking a condition and then we are returning some value so there are zero multiplications for the base case and hence we can say m of 1 is equal to0 why M of 1 we know if n is equal to 1 then we are inside fact of 1 therefore n is equal to 1 and hence we can say that this is M of one because M of 1 represents the number of multiplications required to compute fact of one there are
no multiplications needed to compute fact of one here we are simply returning one when we are within fact of one therefore M of 1 must be equal to zero now what about the else Block in the else block we have return n * fact of n minus one we know the number of multiplications required to compute fact of n is MN therefore the number of multiplications required to compute fact of n n -1 must be M of nus1 and here we are performing one multiplication hence the overall cost will be M of nus1 + 1
the cost is the number of multiplications the number of multiplications required to compute this sub problem is M of nus1 + 1 now we know the number of multiplications required to solve these sub problems now we are ready to write the recurence relation of multiplications this is the recurence relation M of n is equal to M of n -1 + 1 if n is greater than 1 we can observe if n is greater than 1 then only the else block will be executed and n * fact of n minus 1 will be returned from this
function so if n is greater than one then the else block will be executed and we know the number of multiplications required to compute this sub problem is M of n-1 + 1 that is what I have written here now what happens if n is equal to 1 then the base case will be executed and the number of multiplications required here is zero this is the reason I have written zero here so MN is equal to Z if n is equal to 1 so this is the recurrence relation of of multiplications of factorial of n
now as we have written the recurence relation let's move to the next topic where we will discuss how to solve the recurence relation we have obtained using substitution method let's solve the recurence relation we have obtained using substitution method this is the recen relation we have obtained M of n is equal to M of n minus 1 + 1 if n is greater than 1 if n is equal to 1 then M of n will be equal to 0 now let's apply the substitution method to solve this recurence relation according to the substitution method we
need to write the recursive part first so let's write M of n = to M of n-1 + 1 this is the recursive part and I have written this as it is MN is = to MN -1 + 1 now let's substitute M of n -1 by m of N - 2 + 1 because if we replace n by n minus 1 we will get nus 2 here and we will get + 1 here so M of n is equal to M of N - 2 + 1 +1 this + 1 needs to be written
as it is here and M of n minus1 is replaced by m of nus 2 + 1 we can rewrite this as M of nus 2 + 2 now we can substitute M of nus 2 by m of N - 3 + 1 because if we replace n by nus 2 here we will get nus 3 here and + 1 so we will get MN equal to M of N - 3 + 1 + 2 + 2 is written as it is here and M of nus 2 is replaced by m of N - 3
+ 1 this can be Rewritten as M of nus 3 + 3 because 1 + 2 is 3 therefore M of n is equal to M of N - 3 + 3 we can observe a pattern here if we have one here then we have one here as well if we have two here then we have two here as well if if we have three here then we have three here as well so we can continue in this way up to M of n minus K in this case M of n is equal to M
of n minus k + K if we have K here then we must have K here as well according to this pattern now we have written the generalized form MN is equal to mn- k + K now we know M of n represents the number of multiplications required to compute fact of n m of n minus one represents the number of multiplications required to compute fact of n minus1 m of n minus 2 represents the number of multiplications required to compute fact of nus 2 what about M of n minus K it is clear that
M of n minus K represents the number of multiplications required to comp Ute fact of n minus K let us suppose fact of n minus K is the last recursive call then n minus K must be equal to 1 in order to satisfy the base case we know that if n is equal to 1 then the base case is satisfied this is because I'm assuming factor of n minus K is the last recursive call in this case we know the number of multiplications must be zero as n is equal to 1 here we will get
1 this means we will get M of 1 and M of 1 is equal to 0 so we are assuming N - K is equal to 1 therefore we will get M of 1 here and this will be replaced by zero so now let's assume n minus K is equal to 1 then K must be equal to nus 1 therefore we can replace K by n -1 here we will get N - n -1 which isal to 1 so we will get M of 1 here and this K will also be replaced by nus1 so
we will get M of 1 + n -1 now what is M of 1 We Know M of 1 is equal to 0 so here we have 0 + n -1 this is equal to n -1 so M of n is equal to nus1 this means in order to compute fact of n a total of n minus one multiplications are needed and we can represent this using asmic notation M of n can be written as B of n so precisely n minus1 multiplications are needed in order to compute factorial of N and M of n
is ASM totically equal to bigo of n so we have solved the Regence relation of multiplications of factorial of n using substitution method and you can verify this on your own as well that why there are nus1 multiplications let's say we want to calculate factorial of 5 what is factorial of 5 factorial of 5 is 5 * 4 * 3 * 2 * 1 there are a total of four multiplications in case of factorial of 5 similarly 6 factorial is 6 * 5 * 4 * 3 * 2 * 1 here we have a total
of five multiplications so in order to calculate 6 factorial we need five multiplications in order to calculate 5 factorial we need four multiplications it is clear that in order to calculate n factorial we need n minus1 multiplications and that is what we are getting here so we have verified the result as well and this means we have solved our recurence relation correctly so with this we are done with this topic also we learned how to write the recurence relation of multiplications of factorial of N and we also learned how to solve the recurence relation of
multip applications using substitution method now we are done with this lecture okay friends this is it for now thank you for watching this presentation I will see you in the next one [Applause] [Music]
