[Music] let's solve problem number three on recurrences using substitution method here is the problem find the time complexity of the following algorithm this is the algorithm Rec of N and we are required to find the time complexity of this algorithm If You observe carefully this is the recursive algorithm because Rec of n is calling itself within its own body here we are calling Rec of n minus one so clearly this is the recursive algorithm and we already know how to find the time complexity of the recursive algorithm we first need to write the recurrence relation
of time for the recursive algorithm and then we need to solve it using any of the methods which we are available with we know one method to solve the recurrence relation and the method name is substitution method so we will use the substitution method to solve the recurence relation of time of this algorithm as well and this will give us the time complexity eventually we can represent the time complexity using one of the ASM totic notations so now let's try to write the recurrence relation of time of this algorithm first for this let's remove this
problem statement and let's create some space over here for the solution now we have the algorithm in front of us and now we are ready to solve the problem we are required to find the time complexity of this algorithm and we need to write the recurrence relation for this purpose let's now write the recurrence relation of time for this let's assume TN represents the time required to solve Rec of n or the time required to execute Rec of n now we can represent TN in terms of the time required to solve the smaller sub problem
this means we can represent TN in terms of the time required to solve the base case and the recursive case let's focus on the base case first here we have if n equal to 1 then return 1 if it is the case that n is equal to 1 then we will simply return 1 this is the simplest problem to solve if n is one then we are within recre of one and this means the time required to solve this problem is T1 because we have assumed TN is the time required to solve Rec of n
so T1 must be the time required to solve Rec of one if n is equal to 1 then one will be returned from this algorithm and returning one takes constant time similarly comparing these values take constant time therefore the overall time is constant we can assume the constant as capital c but this time we will assume assume the constant as integer 1 why because this is the common practice in many books and in many courses the common practice is to assume the constant time as one so this time let's assume the constant as one so
T1 is equal to 1 this means the base case will take constant amount of time to solve now let's focus on the recursive case in this else block first we are calling the rec of n minus1 function and this will take T of n minus1 time because TN is the time required to solve Rec of n clearly TN minus one is the time required to solve Rec of n minus1 now after this we have this for Loop this is the first time when we are seeing the for Loop in the recursive algorithm and it is
quite common to have the for Loop in the recursive algorithm as well and in this for Loop we can observe I is initialized to 1 I is compared with n and I is incremented by one every time and within this for Loop we have the printer function which will print Neo is love as the for Loop runs how many times this for Loop will run we can observe that the first value of I is 1 the second value will be two then it will be three then four 4 5 6 and so on up to
n so from 1 to n there are a total of n values and hence there are a total of n iterations so clearly this for Loop will run n times and therefore this print F function will also run n times clearly the time consumption in this case is n hence the total time required to solve the recursive case is TN minus1 + n now let us assume that n is positive so if n is greater than 1 then TN must be equal to tnus 1 + n but if n is equal to 1 then TN
must be equal to 1 so the recurrence relation of time is TN = to TN - 1 + n if n is greater than 1 if n is equal to 1 then TN must be equal to 1 so now we have the recurrence relation of time now we are ready to solve this recurrence relation for the remaining part of the solution let's create some space over here by shifting this recurence relation at this place now let's solve this recurrence relation we know we can solve this recurrence relation using the substitution method according to the substitution
method we must start from the recursive part so we know the recursive part is TN = TN minus1 + n this is the starting point now we can substitute tn-1 by tn- 2 + n-1 because if we replace n by n minus1 here we will get TN minus1 in the left hand side and in the right hand side we will get t n - 2 + n -1 so TN is equal to TN - 2 + n -1 + N I have replaced tn-1 by TN - 2 + nus1 and I have written plus n
as it is after this this is what TN is now TN is represented in terms of TN minus 2 we can remove the brackets and this is the expression so obtained TN - 2 + n -1 + n now we can repl tn- 2 by TN - 3 + n- 2 because we can replace n by nus 2 here so TN - 2 will be equal to TN - 2 - 1 which is equal to TN - 3 + nus 2 so after replacing tnus 2 by TN - 3 + n- 2 we will get
TN = TN - 3 + N - 2 + n -1 + n tnus 2 is replaced by TN - 3 + n- 2 and N -1 + n is written as it is after this this is the new TN now we can observe the pattern here we have tnus 3 then we have nus 2 then nus1 and finally nus 0 every time the constant is decremented by one if we are starting from three then we have two as the constant in the next term then we have 1 then we have 0o let's say if
we continue in this way from tnus 3 to TN minus 4 then tnus 5 up to let's say TN minus K this is the last TN I'm assuming TN is equal to TN minus K plus N - K -1 because we know after the constant 3 we we must have the constant 2 so after K we must have k minus1 then we must have K minus 2 every time we need to decrease the constant by 1 so after TN minus K we must have the term n minus K - 1 then n minus Kus 2
in this way we can continue up to n so this is the generalized equation so obtained now we know TN represents the time required to solve solve Rec of n so TN minus K must be the time required to solve Rec of n minus K let us assume Rec of n minus K satisfies the base case this means n minus K must be equal to 1 if n- K is equal to 1 then we know the time required will be constant 1 so TN minus K will be replaced by 1 this is my assumption that
Rec of n Min - K is the last function call and hence the base case is satisfied and therefore we must get one here as the result so n minus K is equal to 1 this is what I'm assuming therefore K is equal to nus1 so we can replace K by n minus 1 everywhere and n- K over here can be replaced by 1 so we will get T1 here and we know T1 is equal to 1 we can eventually replace this by 1 but what about this term N - K -1 we can replace
K by nus 1 here we will get nus 1 - 1 which is equal to N - 2 and after opening the parentheses we will get n minus n + 2 N - n is 0 therefore we will be left with 2 2 so n - K - 1 can be replaced by 2 what about N - K - 2 K can be replaced by N - 1 so we will get N - 1 - 2 N - 1 - 2 is n - 3 after opening the parenthesis we will get N - n +
3 N - n is 0 so we will be left with three here so N - K - 2 is equal to 3 and we know T1 is equal to 1 so we are getting this summation 1 + 2 + 3 and so on up to n this is the summation so obtained this is nothing but the sum of first n natural numbers 1 + 2 + 3 up to n is the sum of first n natural numbers and the formula to calculate the sum of first n natural numbers as we all know is n
into n + 1 / 2 therefore TN is equal to n * n + 1 / 2 we can write TN using ASM totic notation here we have n * n + 1 / 2 in the ASM totic notation we know constant does not matter so we can eliminate the denominator 2 we will be left with n * n + 1 and this is equal to n square + N Out of n sare and n n square is the dominating term as it will grow faster than n therefore TN must be equal to Big of
n² I have written the worst case time complexity of this algorithm which is bigo of n² most of the times we are interested in the worst case time complexity that's why I've used bigo notation here TN is equal to bigo of n² so the time complexity of this algorithm is bigo of n squ we have been told to find the time complexity of this algorithm and we are successful in finding the time complexity using the substitution method so with this we are done with this problem and this means we are done with this presentation okay
friends this is it for now thank you for watching this presentation I will see you in the next one [Applause] [Music]
