Hello friends, welcome to Gate Smashers In this video we are going to discuss what is Recurrence Relation? How do we write Recurrence Relation? And how do we solve it? And to do this whole work we are taking help of Binary Search Algorithm Guys this video is very helpful for your competitive exams, college or university level exams and even for your placements So guys like this video quickly and subscribe the channel if you haven't done it yet and please press the bell button so that you get all the latest notifications So let's start First of all what is Recurrence Relation? Recurrence Relation, from the name we can tell that it is Recurrence Means to call yourself again and again Here a function is calling itself again and again That is why we call it Recurrence Relation Like we are taking help of Binary Search Algorithm Although I haven't written the whole algorithm but I have written the main point here With the help of this we will first write Recurrence Relation Then we will see how we solve it So here I will tell you about Binary Search We use Binary Search Algorithm If I have to search any element in an array But the condition is that the array should be sorted It should be sorted from the beginning So like I have taken a sorted array here 10, 20, 30, 40, 50, 60, 70 Here we have taken first of all array A, I, J What is I? Pointer which is pointing at the first value on the first index And J is pointing at the last So what will be the value of I here? 1 What is the value of J here? 7 1, 2, 3, 4, 5, 6, 7 Which element are we searching for X? That is the value Let's say if I take X here 10 Let's say I am searching for 10 Or let's say we take 30 Let's say we are searching 30 So how will this algorithm work here? Based on that we have to write the Recurrence Relation So here what we are calculating first So this is mid I plus J divided by 2 Means 1 plus 7 divided by 2 So 1 plus 7 divided by 2 8 divided by 2, that is what 4 What does this mean? We are dividing this problem into two pieces Means I have a problem N That N problem Means what is the size of the problem N? We are finding that N problem in the median and dividing it into two parts One part becomes N by 2 Second part becomes N by 2 Simple meaning here See here we have calculated A of mid Now A of mid means whatever element is coming in the middle Whatever element is coming in the middle is equal to X Let's say we searched this And which element will come in the middle? 40 will come The element in the middle is 40 So look which element we are searching for X? Is 40 equal to 30? No So that means I have to take the search ahead If 40, let's say if I am searching for 40 And 40 is equal to 40 Means my searching gets completed here If it gets completed here obviously how much time did it take me? It took a constant amount of time Which you can call order of 1 also Because it took a constant amount of time to find the median And it took a constant amount of time to check this condition But if I am elementing search as 30 Now you will go to the next position What is next? Let's go to the else part If mid is greater than X What is mid? 40 Is 40 greater than 30? Yes, if 40 is greater than 30 if 40 the mid element is greater than 30 What I have to do here? How will this problem get divided? Here we have 10, 20 , 30 And here 50, 60, 70 came whatever was my mid element if 40 is greater than X then I have to apply this binary search if my 40 is less then I had to apply this Means I have to apply one condition of both What does this mean? Which element you are searching That element is smaller than mid If it is smaller than mid Then obviously it will be in this position It will be anywhere in this If that element is bigger than mid Then where will it be? In this problem So what are we actually doing? We are going to one problem of these two Means I divided my N problem total in two parts N by 2, N by 2 Now if my middle element Whatever is my middle element That was any of my elements If the element I am searching for If it is smaller than middle element Then I will search this problem If it is bigger than middle element Then I will go to this problem Let's say if my element is smaller than middle Then I will go to this Now I will not take any interest in this Means you don't have to go towards N by 2 Now what will you do? In this N by 2 again You will put the same funda and find out mid So let's say I did mid find out 1, 2, 3 Means my i is here And my j is here So 1 plus 3 divided by 2 So what will come? Middle element 2 Middle element 2 came So is middle element equal to 30? Because we are searching 30 Is 20 equal to 30? No So I went to next What is next? The middle element we have now is 20 Is 20 greater than 30? No Means I will not go to this position Or I will not solve this problem I will do the next one Means what we are doing? I divided this N by 2 in two parts N by 4 N by 4 Then I am searching Is my element smaller than middle or bigger? Now see my element middle is 20 And 30 is bigger than 20 Means I will not go to this sub-problem I will go to this sub-problem So here you have to find out this trend What are you doing? You are dividing N problem into N by 2 But you are going only towards one N by 2 Then you are dividing it into N by 4 But you are interested in one sub problem Then you are doing N by 8 in N by 8 But you are interested in one sub problem So what will be the recurrence relation? Recurrence relation will come If my problem is T of N Means my total time is T of N So the recurrence relation is T of N by 2 T of N by 2 Because every time I am interested in one of the sub problem Means N by 2 Then in the next iteration N by 4 N by 8 N by 16 Plus some constant amount of time I will apply I will take some constant time Which I will take to find out mid or in simple comparison I will take a constant amount of time here So this is actually a recurrence relation of binary search So in this way, the way we have to move The way we have to move The way the trend is going On the basis of that trend we write the recurrence relation Now the next part comes, how to solve the recurrence relation So to solve it The first method we have is substitution method Or what we call back substitution method Second we have master theorem And third is recursion tree So in the next video we will talk about substitution method Or what you can call back substitution method How we solve the questions through this we will see that Thank You.