Substitution Method to Solve Recurrence Relation of Return Value

[Music] in our previous presentation we learned how to solve the recurence relation of time using substitution method now in this lecture we will learn how to solve recurence relation of return value using substitution method so let's get started with this lecture and let's see the topics the first topic of this lecture is writing the recurence relation of return value first we will learn how to write the recurence relation of return value and then we will learn how to solve the recurence relation using substitution method let's start with the first topic writing the recurence relation of

return value we learned how to write the Regence relation of time and we also learned how to solve the recurence relation of time using substitution method in our previous lectures now we are interested in writing the recurence relation of return value of factorial of n so let's take the same algorithm factorial of n we know if n is one then one will be returned from fact of n otherwise n * factor of n minus1 will be returned we cannot just write the recurence relation of time we can also write the recurence relation of return value

of this algorithm we already learned how to write the recurence relation of time of this algorithm now let's write the recurence relation of return value of this algorithm we already learned what is recurrence relation recall that a recurrence relation is a mathematical expression that describes the cost of the overall problem in terms of the cost of the smaller sub problems in this case we are interested in return value hence the cost is return value so we need to represent present the return value of fact of n which is the overall problem in terms of the

cost or we can say the return value of these smaller sub problems these are the smaller sub problems we will now represent the return value of fact of n in terms of the return values of these smaller sub problems let's see how to do this let's say the return value of fact of n is represented by RN so RN is the return value of fact of n now what about this base case we know this base case is satisfied when n is equal to 1 this means we are considering fact of one we know the

return value of fact of n is RN therefore the return value of fact of one must be R1 and if R1 is there this means if n is equal to 1 then one will be returned from the function this means the return value must be equal to 1 and hence R of 1 must be equal to 1 we need to write the exact return value here return value of the base case is one therefore we must write one here if it is two then we will write two if it is five we will write five

I hope you got the idea so we need to write the exact return value because we are interested in writing the reference relation of return value now we know what is the return value of the base case let's move to the recursive case and let's try to write the return value in terms of R for this recursive case here we have the else block and within this L's block we have return n * fact of n minus1 now how do we represent fact of n minus1 in terms of R we know RN represents the return

value of fact of n therefore R of n minus1 must represent the return value of fact of nus1 so one thing is clear that we can write R of N minus1 and we can multiply it by n and this will be the overall return value as we can observe here we are returning n * fact of nus1 this means we are returning R of nus1 * n because R of nus1 represents the return value of fact of nus1 and we need to multiply it by n as it is indicated over here so this must be

the return value R of n -1 * n so one thing is clear that if n is equal to 1 then R of n is equal to 1 if n is greater than 1 then R of n must be equal to R of n-1 * n now we can easily write the recurrence relation the recurrence relation must be RN = to r n -1 * n if n is greater than 1 otherwise if n is equal to 1 then RN is equal to 1 this is the way we write the recurence relation please keep this

in mind RN has two possibilities if n is greater than 1 then RN is RN - 1 * n if n is equal to 1 then RN is 1 so I hope this idea is clear we now have the recurence relation of return value of this big problem we have represented the return value of fact of n in terms of the return value of the smaller sub problems this is what we can observe here so we have written our recurence relation this is what we learned in the definition of the recurrence relation now as we

have written the recurrence relation of return value of this algorithm let's move to the next topic where we will discuss how to solve the recurence relation which we have obtained using substitution method we know this is the Regence relation so obtained our R of n is equal to R of n - 1 * n if n is greater than 1 otherwise if n is equal to 1 then R of n is equal to 1 this represents the base case and this is the recursive case now let's solve this recurence relation using substitution method substitution method

is easy to follow we need to write the recursive case first which is R of n equal to R of n -1 * n now we can substitute R of nus1 by R of N - 2 * n -1 why you can't replace n by n -1 you will get R of nus1 in the left hand side and in the right hand side you will get R of N - 2 because n -1 - 1 is n - 2 so we will get R of N - 2 * * n -1 this n will be

replaced by nus1 so we can substitute R of N1 by R of N - 2 * n -1 so what we will get the new R of n is equal to R of N - 2 * n -1 * N I have written this part as it is this represents R of N minus1 and this is the new R of n now we can write this as R of n - 2 * n -1 * n this is the expression so obtained so I have written R of n in terms of R of n minus

2 this is how the substitution method works now we can proceed and substitute R of nus 2 by R of nus 3 * nus 2 if we replace n by nus 2 we will get R of N - 2 = to R of n - 3 because n - 2 - 1 is n -3 so we will get R of nus 3 here time N - 2 because n will be replaced by nus 2 so R of n-2 is equal to R of N - 3 * N - 2 so new RN is R of

N - 3 * N - 2 * n - 1 * n we can remove these brackets and this is the expression so obtained so now I have represented R of n in terms of R of nus 3 now we can observe a pattern here here we have R of n -1 * n here we have R of N - 2 * n -1 * n when we have R of nus 3 here then we have N - 2 * n -1 * n here so as we proceed in this way we can continue up

to R of n minus K like this and here we can observe that if we have three here then we have 2 1 and 0er here if we have two here then we have 1 0 here so clearly the constants are decremented by one the next value after R of N - 3 is n - 2 here we have R of n - K so the next value must be N - K -1 then after this we must have N - K - 2 and in this way we can continue up to n so this

is the expression so obtained we have generalized R of n like this as we have observed the pattern here we can easily write this generalized expression now R of n is equal to R of nus K * N - K -1 time N - K - 2 time and so on up to n now we know RN represents the return value of fact of n RN minus1 represents the return value of fact of nus1 r n min-2 represents the return value of fact of nus 2 so we can say R of n minus K represents

the return value of fact of n minus k now let's assume fact of n minus K is the last recursive call and hence the base case must be satisfied what was the base case if n is equal to 1 then return 1 this is the base case of factorial of n algorithm and from the recurence relation also it is clear that RN is equal to 1 if n is equal to 1 this is the base case if n is 1 then return 1 and this means this is the return value when the base case is

satisfied and as I'm assuming that fact of n minus K is the last recursive call therefore n minus K must be equal to 1 then only the base case will be satisfied because if n is equal to 1 then only 1 will be returned and this means base case is satisfied please note that here we have R of n minus K so in place of n we have n minus K therefore n minus K must be equal to 1 in order to satisfy the base case hence we need to assume that N - K is

equal to 1 and from this we can obtain the value of K which is equal to N - 1 now we can replace K by nus1 in this expression we will get R of n minus n -1 * N - n -1 - 1 * N - n - 1 - 2 and so on up to n here we have nus1 within parenthesis after opening the parenthesis we will get N - n + 1 and this is equal to 1 so we will get R of 1 here and we know what is the value of

R1 if n is equal to 1 then R1 is equal to 1 so R1 can be replaced by 1 here we will get R of 1 what about this expression here we have n minus within parentheses n -1 -1 N - 1 - 1 is equal to N - 2 and after opening the parenthesis we will get N - n + 2 N - n + 2 is equal to 2 so we will get 2 here what about this specific expression here we have n minus within parenthesis n minus + 1 - 2 this is

equal to 3 so we are getting this expression R1 * 2 * 3 * up to n what is R1 we know R1 is equal to 1 therefore we can replace R1 by 1 and this is the expression so obtained and we know what is the value of this expression this is n * N1 * N - 2 and so on up to 1 this is equal to n factorial so RN is equal to n factorial we know RN represents the return value of fact of n so the return value of fact of n is

n factorial which is correct because the algorithm is capable of calculating the factorial of N and hence the return value must be factorial of N and that is what we are getting here as well so this proves that the algorithm is capable of returning n factorial through this recurence relation we have obtained this final result and we have used the substitution method to do this in the substitution method we always need to observe the pattern and accordingly we need to write the generalized expression after writing the generalized expression we need to solve it like in

this case we are assuming R of n minus K is the return value of the last function call this assumption is important as we are assuming this belongs to the last function call therefore the base case must be satisfied and because of this assumption n minus K becomes equal to 1 and from this equation we can obtain the value of K and then we can replace the value of K everywhere in this expression this will help solving this expression and in this way we can obtain the final result so this is how the substitution method

works so with this I hope it is clear how to solve the Regence relation of return value of factorial of n using substitution method this means we are done with the second topic and 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] a