Hello Friends! Welcome to GATE SMASHERS! In this video we will solve recurrence relation Using the Substitution Method As we have discussed in the last video about basics of recurrence relation Where we also saw the recurrence relation of a Binary Search So the recurrence relation of Binary search is T of N by 2 plus C If N is greater than 1 Or if I have Only one element in the array given to me Then obviously that is - what we are looking for That means it is the only element you are searching for And that for the small problems or its sub-problems Or its base condition we are using this Otherwise my recurrence equation Will be T of N by 2 plus C Now let's solve this using Substitution Method Then T(N) = T(N/2) + C Now you need to check If this method or function Decreases by Division As at first it was N And now it is N/2 So let's say If I take N/2 Then what happens? This becomes N/4 Yes or No? If I replace N with N/2 here And I replace it here as well Then N/2 will again be divided by 2 So it becomes N/4 And let's pose I'm taking N/4 Means if I replace N with N/4 Then here it becomes N/4 divided by 2 Meaning N/(4X2) That is T(N/8) + C In this way this function Is getting decremented By means of Division So here let's take this as my statement (1), this is equation (2) and that's equation (3) Now what we are going to do is Back Substitution that means We are going to substitute equation (2) in equation (1) Now if I substitute equations (2) in (1) take a look I have T(N/2) in (1) so I will write the value of it here So T(N) now equals T of For N/2 we have calculated the equation so Substitute equation (2) in (1) then comes T of N/4 + C + C Already we have written this here and an extra C is also there So this is how we have to write it So how can I take it as? N/(2^2) + 2C We can write 4 as 2^2 And there is 2C as well Next we have here N/4 I would consider it as N/4 itself Now for N/4 substitute values from equation (3) Take this and substitute here then what happens? T(N/8) + C + 2C which I already have here Then this becomes T(N/(2^3)) + 3C Now you would get to know of the sequence used here See the iteration that the next value comes in as T(N/(2^4)) + 4C which means In the first iteration came this value Next came this one Next will come this one After that will come T(N/(2^5)) + 5C Meaning whatever value is exponent of N will be multiplied to C So you will run this till certain amount of steps, I mean till which value will you iterate Let's say I am running this till 'K' number of steps So I am executing it because the function that we have here I want to eliminate this I have to terminate it so to do so what should I do? Then let's consider I am executing this till 'K' number of steps So after 'K' steps this equation becomes T(N/(2^K)) Because look here First it was 2^2 then 2^3 2^4, 2^5, 2^6, 2^7, 2^8, 2^9, etc. Upto 'K' steps which if I run the program for 'K' times Then there is N/(2^K) Plus If we have 3 here then we will have 3 here as well 4 here means 4 here too Same is the case for 5 and 6 Similarly if 'K' comes here then what would come here? KC, obviously Now here if I want to terminate this function by obtaining 1, I mean To terminate this function then we know that T(1) = 1 But how will we obtain T(1)? How will we get it? To get T(1) Now if I equate N with 2^K meaning if I assume N and 2^K to be equal Then see what happens. T of N by If N = 2^K then here that becomes N divided by N - Plus K multiplied with the already present C Now see N by N becomes - One T(1) + KC which we can put in this way as T(1) = 1 So the value is 1 + KC But time complexity should not be written in terms of 'K' Time complexity should be written in terms of 'N' only Then how can we calculate the value of 'K'? Then take Log here Then it changes to log N = log 2^K So 'K' comes in front Meaning it becomes K log 2 What is the value of log 2? - One So value of 'K' is equal to what now? It's equal to log N Now substitute it here Then it changes to 1 + log N X C Here 'C' and 1 are constants Which can be rewritten as "Order of log N to the Base 2" Order of log N So we have obtained the time complexity of this recurrence relation Which can also be told as Order of log N is the time complexity of Binary Search So this is the method we should use to solve a recurrence relation using Back Substitution Method Thank You!