Solving Recurrences using Substitution Method (Solved Problem 2)

[Music] let's solve problem number two on recurrences using substitution here is the problem determine the return value of the following algorithm this is the algorithm Rec of N and we are required to find the return value of this algorithm in the last presentation we saw this algorithm and we learned to find find the time complexity of this algorithm as well we learned that we need to write the recurence relation of time first and then we need to solve it using the substitution method in order to find the time complexity of this algorithm now we are

required to find the return value of this algorithm for this purpose we need to write the recurence relation of return value of this algorithm and then we need to solve it using the substitution method so now we know the steps let's proceed and let's try to solve this problem for this let's remove this problem statement first and let's focus on this algorithm here we have Rec of N and within this algorithm we have if n equal to 1 then return 1 this is the simplest problem to solve and hence this is the base case the

recursive case is the else block else return two times Rec of n minus1 + n in order to write the recurence relation we need to assume something for rec of n let us suppose RN or Capital RN represents the return value of Rec of n this is my assumption I'm assuming Capital RN represents the return value of Rec of N and this is the convention I'm following throughout I'm assuming capital t as time and capital r as return value this is my convention I'm following you can follow your convention it is up to you you

can choose any letter for the return value or for the time I'm assuming capital r for the return value so Capital RN represents the return value of Rec of n algorithm this is the problem we need to solve now we can represent RN in terms of the return value of the smaller sub problems this means now we need to represent RN in terms of the return value obtained in case of the base case and the return value obtained in recursive case let's first observe the base case here we have if n equal to 1 then

return one from this algorithm value one will be returned when n is equal to 1 so return value is one clearly and n is equal to 1 this means we are within the algorithm Rec of one hence the return value must be Capital R1 so R1 or Capital R1 is equal to 1 this is the return value of the base case now let's try to find the return value of the recursive case here we have return 2 * Rec of n -1 + n we know r n represents the return value of Rec of n

I'm saying RN but what I mean is capital RN I hope you are with me so if RN represents the return value of Rec of n then r n minus one must represent the return value of Rec of N minus1 and we are multiplying it by two and we are adding n to it and we are returning this entire value this means the return value must be 2 * r n -1 + n this is the exact value we are returning so in case of the recursive case we are getting the return value as 2

* r n -1 + n now we know what are the return values of the smaller sub problems let's represent RN in terms of the return values of these smaller sub problems and this will be the recurence relation of return value of this algorithm so the recurence relation of return value is as follows RN is equal to 2 * r n -1 + n this is the return value we obtained in recursive case if n is greater than 1 then only this will be the return value we know if n is not equal to 1

or in other words if n is greater than one then the else block will be executed I'm assuming n is POS positive that's why I'm saying if n is greater than 1 then only the return value is 2 * rn- 1 + n if n is equal to 1 then the return value must be 1 this is what we can observe here so these are the return values in different cases and this is what RN is RN represents the return value of this algorithm and this is the recurence relation so obtained we can compare this

recurrence relation of return value with the recurrence relation of time which we have obtained in the last lecture we observed in case of recurence relation of time we had T of n in place of RN and within the reference relation we had T of n minus1 plus Capital C Capital C represents the constant time T of n minus1 because Rec of n minus1 will take TN n min-1 time if you're assuming that Rec of n takes TN time then Rec n minus one takes TN minus one time and apart from this we are performing multiplication

addition and we are also returning this entire value these operations will take constant amount of time this is the reason why I have added Capital C to TN minus 1 if n is greater than 1 then TN is equal to TN minus 1 plus constant or Capital C in case of the base case that is if n is equal to 1 we saw that we got Capital C here instead of one I'm representing the constant time with capital c this is just my assumption and we know that in case of base case if n is

equal to 1 then we are returning 1 the comparison will take constant time and returning one will also take constant time this is the reason why I had written Capital C in case of recurrence relation of time here now we can observe we are obtaining a different recurrence relation this recurrence relation is the recurrence relation of return value of this algorithm here we have the exact values we are getting 2 * r n - 1 + n if n is greater than 1 this is the exact value we are getting and if n is equal

to 1 we are getting one from this algorithm that is why I have written this recurence relation now I hope it is clear how to write the recurence relation of return value of this algorithm let's now try to solve this recurence relation using the substitution method this will give us the return value so for this let's create some space over here by shifting this recurrence relation to this place now we have some space here to solve this recurence relation let's proceed and let's try to solve this recurrence relation we will use the substitution method to

solve this Regence relation according to the substitution method we need to start with the recursive part this means we need to write RN = 2 * RN -1 + n this is the recursive part as we can observe in this recurrence relation now let's solve this recursive part we can substitute r n minus1 by 2 * r n - 2 + n -1 because if we replace this n by n-1 we will get r n -1 in the left hand side and in the right hand side we will get 2 * r n -1 -

1 which is equal to r n - 2 plus we will get nus1 here because n will be replaced by n minus one so our n is equal to two times within brackets 2 * r n - 2 + n -1 outside brackets + N I have replaced RN -1 by 2 * RN - 2 + N - 1 and I have written the rest of the expression as it is this is 2 * RN -1 + n this is what RN is now we can open the brackets we can multiply 2 by 2 we

will get 2 square here so we will get 2 s * r n -2 and here also we need to multiply n -1 by 2 so we will get 2 * n -1 here so the expression is 2 2 * r n - 2 + 2 * N - 1 + n this is the expression so obtained so this is new RN this RN is written in terms of RN minus 2 this is how substitution method works we need to substitute R of something every time by its value here we have RN minus 2 we

can replace it by 2 * r n - 3 + n-2 the reason is pretty simple we can replace n by nus 2 here we will get nus 3 and here we will get at n- 2 so R n- 2 can be written as 2 * r n - 3 + n- 2 this is what I'm doing here I have replaced rn- 2 by 2 * RN - 3 + nus 2 and the rest of the expression I have written as it is now we can easily open the brackets here we will get 2 Cub

* rn- 3 here we will get 2 2 * N - 2 it is important to m multiply 2 s by this expression also and we can write the rest of the expression as it is so we will get 2 Cub * r n - 3 + 2 2 * N - 2 + 2 * N - 1 + n now we can observe a pattern in this expression here we have 2 cub and within R we have nus 3 here we have the constant three and here also we have three here we have two

and here also we have two The Power of Two is 1 here and within parentheses we have the constant 1 similarly we can write n as 2^ 0 * N - 0 to observe the pattern here so if we have 2 power 0 this means if we have 0 in the power of two then within parenthesis we must have zero we can observe the clear pattern here now if you proceed in this way let's say up to R r n minus k then we will get RN = 2^ K * RN minus K from this

we can observe the same thing in place of three now we have K in both these places then after this we can write + 2^ K -1 * N - K -1 the reason is that after 2 Cub we can observe we have 2 squ if we have the power of 2 as 2 then within parentheses we must have the constant two as here we have the power of 2 as K the next time we must get the power of 2 s k minus 1 and within parenthesis we must have the constant K minus 1

in this way we can proceed up to 2 2 * N - 2 + 2^ 1 * N - 1 + 2^ 0 * N - 0 so this is the generalized expression so obtained now we know RN represents the return value of Rec of n so let's say r n minus K represents the return value of Rec of n minus K and let us suppose Rec of n minus K is the last recursive call therefore n minus K must be equal to 1 in order to satisfy the base case and hence 1 will be

returned this means the return value must be one so our n minus K will be replaced by 1 I'm doing all this because I want to remove RN minus K and I want to solve this entire expression and I also want some value of K for this I'm assuming n minus K is equal to 1 and N minus K is equal to 1 only when the base case is satisfied and this means Rec of n minus K must be the last recursive call so let us assume n minus K is equal to 1 then from

this we can obtain the value of K which is equal to n -1 now we can replace K by nus 1 everywhere and we can replace n minus K here by 1 so we will get R1 here and here we will get 2 power nus1 here we will get 2^ nus 2 * N - n - 1 - 1 N - 1 - 1 is n - 2 after opening parentheses we will get n - n + 2 N - n is 0 and we will be left with 2 here so this expression is 2^

n - 2 * 2 the next value will be 2^ N - 3 * 3 in this way we can continue up to 2^ 2 * N - 2 2^ 1 * N - 1 and 2^ 0 * n - 0 this is the summation so obtained so we can replace this by 2^ nus 1 * R1 + 2^ N - 2 * 2 + 2^ N - 3 * 3 and so on up to 2^ 0 * N - 0 finally we can replace R1 by 1 and this is the final summation so obtained

so RN is equal to this sum now we need to solve this in order to find the value of RN which is the return value of Rec of n this is the problem we need to solve here we have 2^ N - 1 * 1 here we have 2^ N - 2 * 2 the next value will be 2^ N - 3 * 3 here we have 2^ 2 * N - 2 then we have 2^ 1 * N - 1 and finally we have 2^ 0 * N - 0 now observe carefully here we

have 2^ n -1 + 2^ N - 2 + 2^ N - 3 up to 2^ 2 + 2^ 1 + 2^ 0 this is the sum of geometric progression and here we also have 1 + 2 + 3 + 4 and so on up to N - 2 + n -1 + n this means we have the sum of arithmetic progression as well this progression is what we call the arithmetic geometric progression the combination of both arithmetic and geometric progression we don't know how to solve this type of summation we haven't solve this yet

now we will learn how to solve these types of summations let's remove the rest of the part here now our focus is on this summation this is the summation we have now we want to solve this to further simplify the matter let's write this summation starting from this value so RN is equal to 2^ 0 * n + 2^ 1 * N - 1 + 2^ 2 * N - 2 and so on up to 2^ N - 2 * 2 + 2^ N - 1 * 1 I have written the exact series but in

reverse order now let's focus on this series let's try to solve this we know this is the AGP that is arithmetic geometric progression in order to solve these type of series we need to multiply this summation or this series by two so now we are going to multiply the series by two we will get 2 * RN in the left hand side and in the right hand side we will get 2^ 1 * n n + 2^ 2 * N - 1 + 2^ 3 * N - 2 and so on up to 2^ N

- 1 * 2 + 2^ n * 1 if we multiply 2 power 0 by 2 we will get 2^ 1 here if we multiply 2^ 1 by 2 we will get 2^ 2 here and in this way we can continue like this the last value is 2^ n minus 1 if we multiply this by two we will get 2^ n so this is the series so obtained after multiplying this series by two I'm multiplying this series by two because the common difference in the geometric progression that is 2^ 0 + 2^ 1 + 2^

2 and so on up to 2^ n minus 1 is 2 this is the reason I'm multiplying the series by two if it is the case we have 3 power 0 + 3 power 1 + 3 power 2 and so on up to 3^ n minus1 then we will multiply the series by three so now I hope the reason behind multiplying the series by two is clear now let us suppose this is equation 1 and this is equation 2 let's subtract 1 from 2 by subtracting 1 from 2 we will get 2 * RN minus

RN in the left hand side and in the right hand side we will get min - n n + 2^ 1 + 2^ 2 + 2^ 3 and so on up to 2^ n why are we getting this let's properly observe these two series here we have 2^ 0 * n this is just n and here we have 2^ 1 * N - 1 in this series we are starting from 2^ 1 * n we need to subtract the terms where the powers of two are same here we have 2 power 1 here also we

have 2^ 1 so we will subtract these two terms and let us suppose before this term we have 0 so this is 0 + 2^ 1 * n + 2^ 2 * n -1 and so on so we are subtracting 0 and N so we will get 0 - n which is equal to Min - n this is the first term then after this we are subtracting 2^ 1 * n and 2^ 1 * N - 1 if we take 2^ one common from both these terms within parenthesis we will get N - n +

1 and what is n - n + 1 N - n + 1 is 1 so we will get 2^ 1 only that is why I have written 2^ 1 here then after subtracting 2^ 2 * N - 1 and 2^ 2 * n - 2 we will get 2^ 2 only because N - 1 - n + 2 is equal to 1 and therefore we will get 2^ 2 here then we will get 2^ 3 and so on up to 2 power n this is the result so obtained after subtracting 1 from 2 and

what is 2 * RN - RN this is equal to RN so RN is - n + 2^ 1 + 2^ 2 + 2^ 3 and so on up to 2 power n we want the value of RN only so in this way we can find the result of AG GP I hope this idea is clear we are getting RN only and we are interested in finding RN so now let's find out RN here we have Min - n + 2^ 1 + 2^ 2 and so on up to 2^ n from 2^ 1 to

2^ n we can observe this is the geometric progression and we can solve this easily by applying the formula of the sum of geometric progression we know the first term is two the common difference is also two and the number of terms are n from 1 to n now we can apply the formula of the sum of geometric progression which is a * r^ n-1 divide by R -1 where a is the first term R is the common difference and N represents the number of terms and why r^ nus1 / rus1 because this is the

increasing GP not the decreasing GP here we have 2 power 1 then we have 2 power two this value is greater than this value and this value 2^ 3 is greater than 2^ 2 so this is the increasing GP in case of the decreasing GP the sum is a * 1 - r^ n divide by 1 - R but here the sum will be a * r^ n -1 / r - 1 now let's apply the formula here for this let's remove this part of the solution to add some space let's shift this over here

now let's apply the sum of GP to this summation we will get r n = - n + 2 * 2^ N - 1 / 2 - 1 a is 2 R is 2 and N is n only because we have n terms here we know 2 - 1 is 1 and 2 * 2^ n is 2^ n + 1 and we need to multiply this 1 by 2 as well so we will get minus n + 2^ n + 1 - 2 and this is same as 2^ n + 1 - n + 2

this is the return value of this algorithm r n is equal to 2^ n + 1 - n + 2 so we got the return value by writing the reference relation of the return value and by solving it using the substitution method the most important part of this solution is the AG GP that is arithmetic geometric progression the combination of both arithmetic and geometric progression so this is the return value so obtained so we can say the return value of this algorithm is 2^ n + 1 - n + 2 so we have solved 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]