Solving Recurrences using Substitution Method (Solved Problem 5)

[Music] let's solve problem number five on recurrences using substitution here is the problem solve the following recurrence relation TN is equal to 2 * TN by 2 + n if n is greater than 1 if n is equal to 1 then TN is equal to 1 if n is 1 then TN is equal to 1 this represents the base case and TN = 2 TN by 2 + n represents the recursive case here we are checking if n is greater than 1 then TN is equal to 2tn by 2 + n this time we have

the recurrence relation and we need to solve this recurrence relation using the substitution method so let's apply the substitution method to solve this recurrence relation we need to start from the recursive case that is TN equal to 2 * TN by 2 + n how do we solve this recurrence relation let's substitute TN by 2 by 2 TN by 2 2 + n by 2 why here we can replace n by n by 2 we will get TN by 2 in the left hand side if in the right hand side we will get 2 TN

by 2 s because n needs to be replaced by n by 2 we will get n by2 Square here and then we need to replace n by n by 2 here so we will get n by2 here so TN by 2 is = 2 * TN by 2 2 + n/ 2 so now we know what is TN by 2 let's replace TN by 2 by 2 TN by 2 s + n/ 2 so TN is equal to 2 * this is TN by 2 + n TN by 2 is 2 TN by 2 2

+ n by 2 now we can open the brackets and we can multiply two by these two terms we will get 2 s TN by 2 s+ 2 * n by 2 2 * n/ 2 is n so we will get 2 2 TN by 2 2 + n + n what is n + n n + n is 2 N so this is the value of TN in terms of TN by 2 s now let's substitute TN by 2 s by 2 TN by 2 Cub + n by 2 squ if we replace n

by n by 2 squ here we will get TN by 2 s in the left hand side and in the right hand side we will get 2 * TN by2 Cub plus n by 2 s so let's replace TN by 2 s by 2 TN by 2 Cub + n by 2 2 the new TN so obtained is this expression 2 2 * 2 TN by 2 Cub + n/ 2 2 + 2 n after opening the brackets we will get 2 Cub TN by 2b + 2 2 * n/ 2 2 which is equal

to n and + 2 N now we can add n and 2 N we will get 3 n here we can observe that the power of 2 and the constant before n is same in all these cases here we have 2 power 3 and within T also we have 2 power 3 then here we have 3 * n if we have 2^ 2 and also within T we have 2^ 2 then here we will have 2 * n we can continue like this the new value of TN after this value will be 2^ 4 *

TN by 2^ 4 + 4 4 n then we will have 2^ 5 * TN by 2^ 5 + 5 * n in this way we can continue and then we can stop at 2^ K * TN by 2^ k + K * n TN is equal to 2^ K * TN by 2^ k + K * n we have obtained this from this pattern only here we have the power as K now we need to represent K in terms of n because n represents the size of the input for this let's assume n by

2^ K is equal to 1 this means the base case is reached at this point I'm assuming this is T1 so n by 2^ K is equal to 1 from this we can easily obtain the value of K and we know T1 is equal to 1 so we can remove this T function as well so we are assuming n by 2^ K is equal to 1 from this we can obtain the value of K in terms of n we can multiply both sides by 2 power K and here we will get n = 2^ k

now we can take logarithm on both sides because K is in the power of two we want to bring this to the base hence we need to take logarithm on both sides after applying log we will get log n base 2 in the left hand side and log to^ K base 2 in the right hand side we can apply the property of logarithm here log a power B base C is same as B * log a base C so here we will get K * log 2 base 2 which is equal to K because log

2 base 2 is 1 so K is equal to log n base 2 this is the value of K in terms of n now we can replace n by 2 power K by 1 and we know 2^ K is equal to n so we can replace this 2 power K by n now we're getting n * T1 and what about this K we can replace K by log n base 2 so we will get log n base 2 * n or n * log n base 2 now what is T1 T1 is equal to 1

therefore we can replace T1 by 1 and here we will get n * 1 which is equal to n so we are getting the expression n + n * log n base 2 we can observe out of these two terms n log n base 2 is the dominating term because here we have n and here we have n * log n base 2 this value n log n base 2 is greater than n by log n base 2 * so we can say the dominating term is n log n base 2 and hence TN is

Big go of n log n so if TN represents the time required to solve some algorithm then the time required is B go of n log n so with this we have solved this recurence relation 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]