[Music] let's solve problem number four on recurrences using substitution 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 we can observe Rec of n is calling itself within its own body twice clearly this is the recursive algorithm and we know how to find the time complexity of the recursive algorithm we have solved a couple of problems in our previous presentations and now we are quite familiar with how to find the time complexity of any
recursive algorithm we need to follow a simple step-by-step process the first step is to write the recurence relation for time of the algorithm and step number two is to solve the recurrence relation using the substitution method and finally we can represent the result using the ASM totic notation so these are the steps which we can follow in order to find the time complexity of a recursive algorithm now we are going to follow these steps to find the time complexity of this algorithm let's do this let's remove this problem statement and let's focus on this algorithm
here we have Rec of N and the base case is is if n is equal to 1 then return one from this algorithm otherwise this is the recursive case Rec of n minus1 needs to be called then again Rec of n minus1 needs to be called then the for Loop needs to be executed from I = to 1 to n and the increment is done by 1 every time every time this for Loop runs this print F function will be executed and therefore neso is love will be displayed on the screen now let us suppose
TN represents the time required to solve Rec of n or TN is the time required to execute Rec of n if TN represents the time required to solve Rec of n then how much time this base case will take if TN is the time required to solve Rec of n then T1 is the time required to solve Rec of 1 this means n is equal to 1 and there before the base case is satisfied so T1 is the time required to execute the base case how much time the comparison will take here we are comparing
n with one comparison takes constant amount of time and returning a value also takes constant amount of time so the total time is constant hence we can say T1 is some constant let us assume the constant is one for the sake of Simplicity and the this is the convention which is followed in most of the places so T1 is equal to 1 remember that T1 represents the time required to execute the base case what about the recursive case here we have Rec of N minus1 and Rec of n minus1 will take T of n minus1
time because we are assuming TN is the time required to execute Rec of n hence TN minus1 is is the time required to execute Rec of n minus1 this will also take TN minus1 time so the total time is 2 TN minus1 or 2 * TN minus1 now what about the for Loop for Loop will run from I = to 1 to n and the increment is done by one every time so clearly this for Loop will run n times hence the time required to run this for Loop is n so the total time required
to execute the recursive case is 2tn minus1 + n so now we can represent TN in terms of these smaller sub problems TN is equal to 1 if n is equal to 1 TN is equal to 2 TN - 1 + n if n is greater than 1 if n is equal to 1 then the base case will be executed clearly in this case TN is equal to 1 because the time required to execute the base case is constant and we are assuming the constant is one and if n is greater than one then the
else block will be executed this means the recursive case will be executed and the time required to execute the recursive case is 2tn -1 + n therefore TN is equal to 2tn - 1 + n if n is greater than 1 so the recurrence relation of time obtained is TN = 2 TN - 1 + n if n is greater than 1 if n is equal to 1 then TN is equal to 1 so this is the recurence relation of time for this algorithm Rec of n now let's try to solve this recurence relation have
you ever seen this recurrence relation before something similar to this if you recall in problem number two we saw this type of Rec relation if you recall in problem number two we solved this recurence relation RN equal to 2 RN - 1 + n if n is greater than 1 if n is equal to 1 then RN is equal to 1 this is the recurence relation we obtained in problem number two where the algorithm was Rec of N and the return value of the algorithm was 2 RN - 1 + n if n is greater
than 1 it is equal to 1 if n is equal to 1 now this recurrence relation is quite similar to this recurence relation the difference is that in place of capital r we have capital T everywhere in this recurence relation here we have TN = to 2 TN - 1 + n if n is greater than 1 here we have RN = 2 * RN - 1 + n if n is greater than 1 if n is equal to 1 here we have TN equal to 1 here we have if n is equal to 1
then RN is equal to 1 we can observe these two recurrence relations are same except here we have t and here we have R we solved this recurence relation in problem number two and the results obtained was 2^ n + 1us n + 2 this is the return value we have obtained now there is no need to solve this recurence relation as we have already solved this recurence relation in problem number two this is the result so obtained so TN is also equal to 2^ n + 1 - n + 2 because RN is =
to 2^ n + 1 - n + 2 now we know this is the exact value we have obtained but we want to represent TN in terms of the asymptotic notation and for this we can choose the dominating term here here we have 2^ n + 1 we can rewrite this as 2^ n * 2 we can remove the constant 2 as it does not matter we will be left with 2^ n here and here we have Min - n + 2 compared to this expression 2^ n is the dominating term because 2 power n
represents the exponential function and n + 2 is the polinomial function therefore TN is Big of 2^ n therefore the time complexity of this algorithm is Big of 2 power n so this algorithm will take exponential time to execute I hope this idea is completely clear and now we know how to solve these type of problems so with this 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]
