[Music] in our previous lectures we learned how to write recurrence relations or recurrences of any recursive algorithm and we also learned how to solve those recurrence relations now in this presentation we will solve problem one based on recurrences or recurrence relations using substitution method here is the problem determine the time complexity of the following algorithm this is the algorithm Rec of n we can observe this algorithm is the recursive algorithm because in the body of this algorithm Rec of n minus one is called so Rec of n is calling itself within its own body clearly
this is the recursive algorithm and we learned how to find the time complexity of the recursive algorithm in order to find the time complexity of the recursive algorithm we need to write the recurrence relation of that algorithm first and then we can solve that recurence relation using the substitution method we learned just one method to solve the recurrence relation but there are many methods to solve the recurrence relation we will learn those methods as we proceed in this course but right now we are familiar with the substitution method so let's try to write the recurence
relation of time of this algorithm and let's try to solve the recurrence relation using the substitution method we need to write the recurrence relation of time because we are required to find the time complexity of this algorithm so now we know what are the steps involved we need to write the recurence relation first and then we need to solve it using the substitution method let's remove this problem statement and let's focus on this algorithm and let's try to solve it here we need to find the time complexity let's first write the recurence relation of time
here we have Rec of N and within this we have the base case and the recursive case the base case is if n is equal to 1 then return one from this algorithm otherwise return 2 * Rec of N - 1 + n now how do we write the recurence relation of time of this algorithm it is simple we already know how to do this according to the definition of the recurence relation a recurrence relation is a mathematical expression which is used to describe the cost of the overall problem in terms of the cost of
the smaller sub problems here the cost is time so let us suppose that the time required to solve this algor gorithm Rec of n is T of n now we need to represent TN in terms of the time required to solve these smaller sub problems that is we need to represent TN in terms of the time required to solve the base case and the time required to solve the recursive case now let's start with the base case here we have if n equal to 1 then return 1 returning some value takes constant amount of time
and the comparison also takes constant amount of time therefore T of 1 is equal to some constant let's say C so T of 1 is equal to C why am I saying T of 1 is equal to C we know TN represents the time required to solve Rec of n if n isal to 1 then we know we are at Rec of 1 and hence the time required to solve Rec of 1 will be T of 1 and the time required to solve T of 1 is constant that's why T1 is equal to C now
what about the recursive case this is also the sub problem here we have return 2 * Rec of N - 1 + n we know the time required to solve Rec of n is T of n therefore the time required to solve Rec of n minus1 will be T of nus1 1 and here we are multiplying Rec of nus1 by 2 this will take constant time because multiplication takes constant time and we are also adding n to it and this will also take constant time because addition also takes constant time and returning the entire value
will also take constant time so T of nus1 will be the time required to solve Rec of N minus1 and the additional time required is constant therefore the recurrence relation of time is as follows TN is equal to TN - 1 + C if n is greater than 1 if n is equal to 1 then TN is equal to C this is the base case TN equal to C we know if n is equal to 1 that's what I have written here then the time required is constant if n is greater than one this means
if L's block will be executed then the time required to solve this recursive algorithm will be T of nus1 + C so this is the recurrence relation of time of this algorithm now we need to solve this recurence relation using the substitution method let's do this now let's create some space over here for the rest of the solution for this let's shift this recurrence relation over here now we have some space to solve this recurence relation in order to solve this recurrence relation or this recurrence using the substitution method we need to start with the
recursive case that is TN = TN minus1 + C here we have TN = to TN minus1 + C now we are ready to apply the substitution method according to the substitution method we can substitute tn-1 by tnus 2 + C 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 TN - 2 + C so TN -1 is same as TN - 2 + C therefore we can substitute TN minus1 by tnus 2 + C so new
TN is TN - 2 + C + C we are writing plus C as it is here and TN minus1 is replaced by tnus 2 + C we can rewrite this expression as TN - 2 + 2 C because C + C is 2 * C so TN is equal to TN - 2 + 2 * C now we can substitute TN - 2 by TN - 3 + C because if we replace n by nus 2 here we will get tn- 3 here and we will get C here so TN - 2 is equal
to TN - 3 + C so let's replace tnus 2 by tnus 3 + C and the new TN so obtained is tnus 3 + 3 C because C + 2 C is 3 C now the pattern is clear here we have 1 and here we have 1 * C here we have two and here we have 2 * C here we have three and here we have 3 * C so if you proceed like this up to TN - K here we must have K * C so TN is equal to TN minus k
+ K * C this is the generalized expression now we know T and represents the time required to solve Rec of n TN minus1 is the time required to solve Rec of n min -1 TN minus 2 is the time required to solve Rec of n minus 2 so TN minus K must be the time required to solve Rec of n minus K let us assume Rec of n minus K is the last recursive call this means the base case must be satisfied and this means n minus K must be equal to 1 then only
the base case will be satisfied and one will be returned we know that for TN if n is equal to 1 then constant amount of time will be required to solve the problem we are assuming n minus K is equal to 1 therefore we will get T1 here and we know T1 is equal to constant so this will be replaced by constant c as we have a assumed N - K is equal to 1 then K must be equal to N - 1 so now we can replace n minus K by 1 here and we
can replace K by nus1 here so we will get T1 here and N minus1 here at this point we have TN equal to T1 + n -1 * C now here we have n -1 * C we will get n * C minus C here and here we will get C because T1 is equal to C now we have C + n * C minus C we can cancel these two terms and we will be left with n * C so TN is equal to n * C ASM totically we can write this as big
of n so TN is equal to b o of n we have eliminated the constant C we are left with n that's why I have written big of n here this is the worst case time complexity and worst case time complexity can be represented using the Big O notation and the best case happens when n is equal to 1 if n is equal to 1 then one will be returned and hence the problem will take constant amount of time so in that that case TN will be constant and therefore the best case complexity will be
Omega of one so TN is Big of N and we are interested in the worst case time complexity that's why I've mentioned this in bigo notation so we know this is the amount of time needed to solve this problem so we now know the time complexity of this algorithm is Big go of n so we have solved this problem successfully we now know what is the time complexity of this algorithm we just followed a simple step-by-step process first we wrote the recurence relation of time of this algorithm and then we solved that recurence relation using
the substitution method and eventually we got the time complexity of this algorithm which is B of n so with this we are done with the 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]
