Substitution Method to Solve Recurrence Relation of Time

[Music] in the last lecture we understood the steps involved in analyzing a recursive algorithm there are a total of three steps in order to analyze an algorithm step number one is to write the recurrence relation of the recursive algorithm step number two is to solve the recurrence relation and step number three is to represent the result of the recurence relation using the ASM totic notation we have already completed step number one we learned how to write the recurrence relation of the recursive algorithm in the last lecture we took an example of the factorial of N

and we learned in the last lecture how to write the recurrence relation of time of factorial of n now in this lecture we will learn how to solve that reference relation of time using substitution method this is one of the methods available to us and this method allows us to solve the recurrence relation of time which we have obtained in the last lecture so this lecture is in the continuation to the previous lecture I am assuming you have already watched the previous lecture if not then please watch the previous lecture before moving on to this

lecture so now let's proceed and let's see what are the topics the topic of this lecture is solving the recurence relation of time using substitution method this means we will cover step number two that is to solve the reference relation and not only this we will also cover step number three this means we will learn how to represent the result of the recurence relation by using the asymptotic notation so first we will complete step number two and then we will complete step number three let's see those steps once again these are the steps involved in

order to analyze recursive algorithms step number one is to write the recurrence relation of the algorithm precisely the recursive algorithm step number two is to solve the recurrence relation and step number three is to represent the result of the recurence relation using the ASM totic notation we have completed step number one in the previous lecture now we will complete these two steps in this lecture so let's proceed and let's learn how to solve the recurence relation of time of factorial function and that two using the substitution method this is the recursive algorithm to calculate factorial

of N and this is the recurence relation of this algorithm TN = tnus 1 + C if n is greater than 1 TN = to C if n is equal to 1 now our job is to solve this recurence relation using the substitution method according to this method we need to start from the recursive case that is we need to start from TN = tnus 1 + C so let's write this here TN = tnus 1 + C now we need to solve this mathematical expression using the substitution method so let's do this now we

have TN equal to TN -1 + C here we can observe that tnus 1 can be replaced by TN - 2 + C because we can replace n by nus1 here we will get N - 2 because of this reason and therefore we will get tn- 1 = TN - 2 + C so we can replace or substitute TN minus1 by TN - 2 + C this is the reason why this method is called substitution method we are substituting TN -1 by tnus 2 + C so we will get TN = to TN - 2

+ C + C I have substituted TN -1 by TN minus 2 + C within brackets I have mentioned this and I have written plus c as it is after this this is the value of TN so TN is equal to TN minus 2 + C + C C + C can be written as 2 * C so we can rewrite this expression as TN - 2 + 2 * C so TN at this moment is equal to TN - 2 + 2 * C this means we can write TN into terms of tnus 2

like this now in the same way we can substitute TN minus 2 by tnus 3 + C in the same way we did for TN minus1 so now let's replace tn- 2 by tnus 3 + C this is what we got tnus 3 + C + 2 C I have written plus 2 c as it is so TN is equal to 2 TN - 3 + C + 2 C we can rewrite this expression as tn- 3 + 3 C because 2 C + C is 3 C so we will get tnus 3 + 3

* C here we can observe a pattern we have TN = to TN - 1 + C in the first iteration then we have TN = TN - 2 + 2 C then we have TN = tnus 3 3 + 3 C so we can continue in this way and we can write TN as TN minus k + K * C here I'm assuming some K and if we have K here then we must have K here as well because as we can observe if we have three here then we have three here as well

if we have two here then we have two here as well if we have one here then we have one here as well similarly if we have K here then we have K here as well so TN can be written as TN minus k + K * C now what are we doing here exactly If You observe here we have t of n equal to T of n -1 plus some constant this means time required to solve fact of n or time required to solve factorial of n is same as time required to solve factor

of n minus1 plus some constant so T of n depends on T of n minus1 plus some constant what about t of n minus1 We have replaced T of n minus1 by T of n -2 plus constant here this means in order to find the time to solve fact of nus1 we need to find the time required to solve fact of n minus 2 so T of n minus1 is same as T of nus 2 plus some constant similarly T of n minus 2 is same as T of nus 3 plus some constant we can

proceed in this way and let's assume that t of n minus K is the time required to solve fact of n minus K or factorial of n minus K this is from the assumption that t of n represents the time required to solve factorial of n so T of n minus K must be the time required to solve factorial of n minus K let us assume that fact of n minus K is the last recursive call and therefore the base case must be satisfied remember what's the base case according to the base case if n

is equal to 1 then we will return 1 so this means T of 1 must be equal to constant if we are saying that t of n minus K is the time required to solve the last recursive call which is fact of n minus k then n minus K must be equal to 1 in order to make this T of 1 we want to satisfy the base case and for this we need to assume n minus K must be equal to 1 so I'm I'm assuming here N - K is = to 1 therefore K

is = to N - 1 so we can replace K by n minus1 here this is what we are getting we are replacing this K by n minus1 here and we are replacing this K also by nus1 so we are getting TN equal to TN - n -1 + n -1 * C what is n- N - 1 we will get N - n + 1 which is equal to 1 so we are getting T of 1 here and that's what we want at this point we can observe that n is equal to 1 so

from T of n minus1 we have approached to T of 1 this means we have approached the base case and if base case is satisfied that is if n is equal to 1 then we know return 1 will be executed and this will take constant amount of time therefore T of 1 is equal to Capital C so we can replace this by Capital C and now we have C + n -1 * C so at this moment we can observe TN isal to C + n -1 * C now we can expand this this will

become n * C or C * n minus C here we have C and here we have minus C we can cancel these two terms and we will be left with C * n so TN is equal to C * n this is the final expression so obtained so in this way we have solved this Regence relation using the substitution method let's recall what we have done so far we have started with TN = TN - 1 + C then we have replaced TN minus1 by tnus 2 + C because we know the time required

to solve fact of nus1 is same as the time required to solve fact of nus 2 plus some constant so we have replaced TN minus1 by tnus 2 + C and we have written plus c as it is so TN is same as T of n- 2 + 2 * C in the same way TN is also same as T of nus 3 + 3 * C and in this way if we proceed then we can say that TN is equal to T of n minus k + K * C I'm assuming that fact of

n minus K is the last recursive call if 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 at this moment the base case must be satisfied because this is our assumption that t of n minus K is the time required to solve the last recursive call which is fact of n minus K so n minus K must be equal to 1 if it is equal to 1 then we will get K as n minus 1 so we can replace

this K by nus - 1 and this K by nus1 we will get T of 1 here and N -1 * C here so TN is equal to T1 + n -1 * C and what is T1 we know if n is equal to 1 then we will get T1 here and T1 is equal to C so we can replace T1 by C so we will get the expression C + n -1 * C and what is C + n -1 * C it is equal to C * n so TN is C * n

so in this way we can use the substitution method to solve the recurrence relation that we have now we know how to solve the recurrence relation we are done with step number two let's move to step number three where we will learn how to read represent the recurence relation or the result of the recurence relation using the asymptotic notation this is Step number three representing the recurence relation now here we got TN = C * n what is C * n we can write this in ASM totic notation as well this is C * n

and it is same as Big O of n so the worst case time complexity to solve the recursive algorithm for finding the factorial of n is bigo of n so we have represented time in terms of ASM totic notation and this is our time complexity so the time required to solve the factorial of n is Big of n in this way we have analyzed our algorithm for finding factorial of a number so we have completed all the three steps and hence we are done with this topic solving the recurence relation of time using substitution method

we have learned how to solve the recurence relation of time of factorial of n using substitution method and finally we have represented the result using ASM totic notation so with this 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]