Dear students, welcome to Great Smashers. In this video, I am going to explain recursive tree method to solve the recurrence relations. So guys, to solve recurrence relations, we have already done with the back
substitution method and master theorem. But guys, let me tell you, there is a third method also to solve recurrence relations. That is recursive tree method. Whenever we use divide and conquer techniques, then our problem is dividing into sub problems.
And later, we combine the answers of sub
problems and reach the final output. So in these methods, we can use recursive
tree method to solve recurrence relations. So guys, with example, I will give you a
clarity of all the concepts of the scene. So guys, like the video quickly and subscribe the channel. if you have done it, then you
can subscribe with more devices. Subscribers are very important. So let's start. First of all, I will explain you with
a very simple recurrence relation. So that you get clear concept first. Then I will solve 2-3 more recurrence relations related to this. So here, the recurrence relation that we
have written is written as merge sort. So what we have to do is, our method is recursive tree. Recursive tree. So tree, you know about tree data structure. So here, what we will make is, we will
use the concept in the form of tree. So in this, first of all, you have to see
that our tn, our function t of n, what is happening is, it is dividing into two parts.
n by 2, n by 2. Means our main problem is dividing into
two subproblems of n by 2 and n by 2. Okay? And if we want to make it, then how will we make it? That my problem is n, it is dividing
into two parts, n by 2 and n by 2. Okay? So I divided these two subproblems, first of all, the big problem. After dividing, I will combine their answers and their results. So how much is my cost of dividing and combining? cn. So here cn can be given, order of n can also be given. So whatever is given, we got to know that
to do this step, division and combine, how much cost will I have? cn. Where c is what? Your constant. What is c? It is constant, so don't take much tension about it.
But write it together. So c.n. Now see, my n will be divided into n by 2 and n by 2. Now what will happen in the next step? This n by 2 will be divided into n by 4 and n by 4. Okay? So n by 2, now instead of n, if you put n by 2, then what will happen? It will become n by 4, right? So it means it is divided into two subproblems, n by 4 and n by 4. So obviously, what will happen to this n by 2? It will be divided into two subproblems, n by 4 and n by 4. Okay? So if you put n by 2 instead of n, then it will become n by 4.
Simple thing. So here n by 4 and n by 4,
these two subproblems are coming, if I combine these, then how much will cost me? It will cost n by 2. How did you know? See, here my original problem was n. And what did it take to combine it? My time was n. Now what did I do? That my subproblem, its size is n by 2 size. So it is n by 2 size. So obviously, my cost will be n by 2. Now see here, it is n by 4. n by 4 is the size of one, the other size is also n by 4. So n by 4, what happened to n by 4? It became n by 2. So to combine these two, n by 2. To combine these two, n by 2. So what will be your total? N cost will be here. Means if you add all four,
then how much will be my cost? N cost will be here. In the next case, what will happen? This n by 4 will be divided into n by 8. All of it will be divided into n by 8 and n by 8. So again, when you combine all these sub problems, then how much will be my cost? N cost will be again applied.
So here a scenario is getting clear to you. That the original problem is n/2, n/2 is n/4, n/4 is n/8. By doing this, how much will be the size of your last subproblem? 1 will be left. So here, till now, how much cost did I get? In these three steps, how much cost did I get? Cn plus Cn plus Cn. Means how much cost did I get? 3Cn is my cost here. See, only in this cost, n, here n, here n. So it means 3Cn. So here you have to keep an important point in mind. That on this step, you got to know n. On this step, you got to know n. On this step, you got to know n. But guys, how much times will this n come? How will you know that? Here you have written 3. Because we have written only three steps.
So 3Cn is my cost. But guys, I will not be able to make it so big. So obviously, what will happen here? Here you can simply say that on what value it depends on the height of the tree. Means how much will be the height of this tree? It depends on that how much will be its answer here. So how will you find the height? You must be seeing that let's say if my problem is n.
It is dividing by n by 2. n by 2 is n by 4. So if I take n value as 16. So next time, what is the size of the problem? 8. Next time, what happened to it? 2. Next time, sorry 4. Next time what happened to it? 2. Means my problem is if let's say I take its size as 16. Then next time it will be divided and will remain in 8. After that it will be in 4. After that it will be in 2. After that it will be in 1. Means you are finding the height from here. 1 2 3 4 So if you take log 16. So if you do log 16 base 2, what will be the answer? 4. So see this scenario is getting cleared to you. So in this, your function is which series is being made in this? Log n here.
So what is the function made here? Log n. So means this value is in the first step n so how much will it go ahead? Depending on the height. So how much is the height in this? Height is being made as your log n. So means this Cn how much time will it come? Cn will come to you log n time. So means its total cost is how much? To solve this recurrence relation. Total cost will be C.nLogn. Where C is what? Constant. So what can we write it? We can write it big O or you O n log n. Big O of n log n. Because C is obviously simple constant. So big O of n log n. We can find out its time complexity in this way. So you just have to keep this scenario in mind.
That how your tree is going. How much height is going. And how much cost is being incurred on every step. Just find out those two values. You can easily solve any question. Thank You..