Solving Recurrences using Substitution Method (Solved Problem 6)

[Music] let's solve problem number six on recurrences using substitution here is the problem solve the following recurence relation tnal to squ < TK of n tunk of n + n if n is greater than 2 if n is equal to 2 then TN is equal to 2 this is the recurrence relation and we need to solve this recurence relation this time the algorithm is not given we do not have to write the recurence relation and then solve it using the substitution method this time we have the recurence relation and we need to solve this recurrence

relation using the substitution method so now let's try to solve this recurence relation using the substitution method we know according to the substitution method we need to start from the recursive case that is TN = to square < TK of n tunk of n + n so let's start from TN = to S < TK of n tunk of n + n this is the big problem to solve the small problem is TN = to 2 if n is equal to 2 if n is 2 then TN is a constant and this constant is two

this is the small problem and hence this represents the base case we are starting from the recursive case according to the substitution method now let's substitute tunk of n by squ otk of otk n * tunk of < TK of n+ squ < TK of n we know we can represent square root of n as n^ 1X 2 so we can replace < TK of n by n^ 1X 2 here also we can replace root of n by n^ 1 by 2 so TN is same as n ^ 1X 2 * t n ^ 1X

2 + n now in place of T n^ 1X 2 we can write n^ 1X 4 because square root of root of n is same as n^ 1X 2 * 1X 2 1X 2 * 1X 2 is 1x 4 so we will get n^ 1X 4 and here also within parenthesis we will get n^ 1X 4 because n will be replaced by square root of n this is squ root of squ root of n again this is n^ 1x 2 * 1X 2 so we will get n^ 1X 4 here so this is T n^

1X 4 then here we will get square root of n or we can write it as n^ 1 by 2 so clearly T squ root of n or t n^ 1X 2 is same as n^ 1X 4 * T n^ 1x4 4 + n^ 1X 2 so this is the new TN so obtained here we have written n^ 1X 2 as it is this is square root of n we are writing it as it is and then we have tqu < TK of N and then + n according to this expression tunk of n is

replaced by n^ 1X 4 * T n^ 1X 4 + n^ 1X 2 now we know this is the new new TN in terms of T n^ 1X 4 now we need to multiply n^ 1X 2 by n^ 1X 4 * T n^ 1X 4 and we need to multiply n^ 1X 2 by n power 1X 2 now let's open these brackets and let's multiply n^ 1X 2 by these two terms here we will get n^ 1X 2 * n^ 1X 4 * TN n^ 1X 4 what do we get from here what is the

multiplication of n^ 1x 2 and n^ 1X 4 we know when the bases are same then the powers will add so we need to add 1X 2 and 1X 4 1X 2 + 1X 4 is 3x 4 so we can write n^ 3x 4 here so we'll get n^ 3x 4 * tn^ 1X 4 and then we need to multiply n^ 1X 2 by n^ 1X 2 we know here the bases are same so the powers will add and 1X 2 + 1X 2 is 1 only so we will get n^ 1 here this means

we will get n here now we have n + n and n + n is equal to 2 N so we will get 2 N here so this expression is same as n^ 3x 4 * t n ^ 1X 4 + 2 N now let's substitute tn^ 1X 4 by n^ 1X 8 because square root of n^ 1x 4 is same as n^ 1X 4 * 1X 2 so in the power 1X 4 is Multiplied to 1x 2 we will get 1X 8 as the power of n so we will get n^ 1X 8 *

t n^ 1x8 + n^ 1X 4 because n should be replaced by n^ 1X 4 so tn^ 1X 4 is same as n^ 1X 8 * T n^ 1X 8 + n^ 1X 4 so new TN is equal to n^ 3x 4 * tn^ 1X 4 + 2 N this is TN ^ 1X 4 which is same as n^ 1X 8 * T n^ 1X 8 + n^ 1X 4 now we need to open these brackets and we need to multiply n^ 3x 4 by n^ 1X 8 and n^ 3x 4 by n^ 1X 4

what is the multiplication of these two terms here we know the bases are same so we need to add the powers 3x 4 + 1 by 8 is same as 7x 8 we can follow the same process which we have followed for 1X 2 + 1X 4 in the same way we can add 3x 4 and 1X 8 we will get 7x 8 so we will get n^ 7x 8 here and n^ 7x 8 will be multiplied to T n^ 1X 8 and here we have n^ 1X 4 we now need to multiply n^ 1X

4 by I n^ 3x 4 what is the addition of 3x4 and 1X 4 we need to add these two Powers because the bases are same 3x 4 + 1X 4 is same as 4X 4 and 4x 4 is equal to 1 so we'll get n Only and n + 2 N is 3 n so the new expression so obtained is n^ 7 by 8 * tn^ 1X 8 + 3 n this is the value of TN now we can see the pattern here we have n^ 1X 2 here we know square root is same

as 1X 2 so it is n^ 1x 2 and this is n^ 3x 4 and here we have n^ 7 by 8 we can observe in the power of n the denominator is always the powers of two here in the power the denominator is 2 which is 2 power 1 here we have 4 which is 2^ 2 here we have 8 which is 2^ 3 so it is clear that the denominators are always 2 power something and what about the numerator here we can observe the numerators are always one less than the denominators here we

have three because we have four here here we have seven because we have eight here here we have one because we have two in the denominator so clearly if the denominator is 2 power some k then the numerator must be 2 power K minus 1 so this part is clear now what about TN power something here we can observe we have tn^ 1X 4 these two denominators are same here also these two denominators are same so it is clear it is T n^ 1 by 2^ K as we are assuming the denominator of the power

of n is 2 power K so here also we will have 2 power K now what about the remaining part here we have + 3 n in this case we have + 2 N in this case we have plus n so it is clearly K * n because here we have 1 by 2^ 3 here we have 1 by 2^ 2 we know we are representing the power of 2 as K and here we have have 2^ 3 because the power of two is three here also we have three here we have 2^ 2 because

the power of 2 is 2 here we have 2 here we have 1 by 2 as the power of n and this means the power of two is 1 that is why we have one here so it is clear this is K * n so if you proceed in this way then the generalized expression is in this form TN is n^ 2^ K - 1 / 2^ K * T n^ 1 by 2^ k + K * n this is the equation so obtained now we need to represent K in terms of n because n

represents the size of the input and eventually we want to represent TN in terms of the ASM totic notation where we need to represent it in terms of the input size hence it it is important to represent K in terms of the input size also we need to eliminate TN power 1X 2^ k for this let's assume n^ 1X 2^ K is equal to 2 this means the base case is reached then only n^ 1X 2 power K will be replaced by 2 here we can observe if n is 2 then we will get T2

here here in place of n we have n ^ 1X 2^ K so we need to assume n^ 1X 2^ K as 2 we will get T2 here and T2 is equal to 2 So eventually tn^ 1X 2^ K will be replaced by a constant and the constant in this case is 2 so let us assume n^ 1X 2^ K is equal to 2 now from this we can easily find the value of K in order to find the value of K we need to bring K to the base and for this we know what

we need to do we need to take log on both sides here we have the constant two so we will take log base 2 on both sides here we will get log n^ 1X 2^ K base 2 and in the right hand side we will get log 2 base 2 so the left side is log n^ 1X 2^ K base 2 and the right hand side is log 2 base 2 what is log 2 base 2 log 2 base 2 is 1 what about log n^ 1 by 2^ K base 2 we know the property

of logarithm log a power B base C is same as B * log a base C so 1X 2^ K comes in front of log n base 2 so we are getting 1X 2^ K * log and base 2 in the left hand side and one in the right hand side of the equation now how do we solve this it is simple to solve this type of equation we need to multiply 2^ K on both sides in this way we can remove this denominator we will get log n base 2 in the left hand side

and 2 power K in the right hand side this is the equation so obtained log n base 2 is same as 2^ K now we know we want to find the value of K and K is in the power of 2 we need to bring k a to the base for this we will take log once again and this time also we will take log base 2 on both sides because here the constant is two so let's take log base 2 on both sides after applying log base 2 on both sides we will get log

n base 2 log base 2 in the left hand side and log 2^ K Bas 2 in the right hand side so this is the equation so obtained we know log to ^ K base 2 is same as K * log 2 base 2 which is equal to K that's why we're getting K here and here in the left hand side we have log n base 2 log base 2 so this is the value of K in terms of n now here we can observe that 2^ K can be replaced by log in base 2

directly so we can replace 2^ K by log n base 2 we will get n^ log n base 2 - 1 divide by log in base 2 now we can replace n^ 1 by 2^ K by 2 we will get T2 here and T2 is equal to 2 we already know this from this recurence relation so we can replace tn^ 1 by 2^ K by 2 so this is the expression so obtained we are getting n^ log n base 2 - 1 / log n base 2 * 2 and here we have K * n

we know what's the value of k k is equal to log n base 2 log base 2 so let's replace K by log n base 2 log base 2 here we are getting n * log n base 2 log base 2 now let's focus on this fraction here we have log n base 2 - 1 divide by log n base 2 we can rewrite this as 1 - 1 by log n n base 2 so in place of log n base 2 - 1 IDE log n base 2 we can write 1 - 1 by

log n base 2 now we can rewrite this as n^ 1 / n^ 1 by log in base 2 because the sign here is minus if you have plus here then it will be n^ 1 * n^ 1 by log n base 2 but as we have minus here we will get n^ 1 IDE by n^ 1 by log n base 2 so this is the fraction so obtained now the interesting part here we have n^ 1 by log n base 2 we know n^ 1 by 2^ K is equal to 2 and what is

2^ k 2^ k is log n base 2 so we can replace 2^ K by log n base 2 we will get n^ 1 by log n base 2 = 2 here also we have n^ 1 by log n base 2 so we can replace n^ 1 by log n base 2 by 2 so we will get n by 2 * 2 here we can easily cancel 2x 2 we will get n here so the expression so obtained is n + n * log n base 2 log base 2 now what do you think out

of these two which is the dominating term here we have n * 1 one is the constant here we have n * login base 2 log base 2 login base 2 log base 2 is the logarithmic function we know the growth rate of the logarithmic function is greater than the growth rate of the constant function in both these terms n is common but this is n * 1 and this is n * log n base 2 log base 2 here n is multiplied by the constant function and here n is multiplied by the logarithmic function

clearly the growth rate of n * the logarithmic function is greater than the growth rate of n * the constant function therefore this is the leading term here and hence TN is equal to P of n log log n TN is represented based on the leading term which is n log log n there is no need to write the bases we can write the asymptotic notation like this in the ASM totic notation we do not have to mention the bases and the constants that's why we have n log log n here so TN is Big

go of n log log n now we have understood how to solve these type of complex recurence relations and that two using the substitution method so with this we are done with this topic and 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]