I have watched several tutorials on this topic past two hours and this one is by far the best. Finally understand how to solve this type of problems. Thank you!!!
Sir, you are the best. I watched your other video on the master method and now this video, and everything makes sense. You cover so many different examples that it’s enough to fill my understanding of how the problem works, and you explain each thing so well that and slow enough so I can understand. Thank you, I have an exam today and this really helps 🙏
Your way of teaching is really in depth and covers the max topic... it really gonna help me in my semester exam... I am really grateful and thankful to your hardwork please sir make more n more videos like this....your the only one in this universe who provided this very good topic for free..and in depth..Thank you sir🙏
The total levels of interior nodes in all examples is K, from level 0 to level k-1. In example 1, since cost at each level is same, we multiply K with n. In example 2, the formula goes from 0 to k-1, which is also K.
Hi, why is the depth k and not k+1, for example like a input of n = 32 and we reach a point where we know n/2^k = T(1). so 32/2^5 = 1. However, arent we excluding level 0, meaning the depth should be k+1?. And if we are excluding it, why did you incldue it back again when calculating the total cost starting from level 0 all the way to k-1? Thank you
Hello Sir. While talkin about the calculation of Lc (Example 1) , you haven't mentioned the cost of a leaf node. Is the cost 1 because T(1) = T(1/2) + 1
@@DrMHJamal Also Sir, in Example 4, we only have RST nodes that contributes to the depth. Isn't it true that at the actual kth level only 2 T(1) nodes will be there? So why are we taking 2^k?! After all, the tree isn't a complete binary tree
@@shubhampathak4206 We are working on the worst-case scenario and finding the maximum number of leaves that can exist in the tree. Actually, the total leaves will be less than that. Similarly, Interior nodes will be less at each level than what we are computing, especially deep down the tree. That is why in example 5 we say that the final solution is ambigous. So we are trying to figure out which out of Ic and Lc is the major contributing factor to the total cost. In example 4, it is clear but in example 5 it is not. Hope that helps.
i have a doubt in the first example for Ic u have taken K. n but in the second example u have taken sum of all the terms and also u have taken GP of infinite terms Doubt 1: why did you take infinite terms Doubt 2: why didn't you take K.N for second example
For doubt 1, see the last slide. For doubt 2, in first example, there are k levels each of cost n making it k.n. In the example 2, each level cost is different so you cannot use k.n. You will have to apply geometric series formula to add the terms.
Hello i have a question. I have read on my book that the recursion tree is used to generate a good guess that is then verified with substitution method. Is it possibile to use the recursion tree alone or do i have to always check the result via mathematical induction?
Can we say the following: The total work done by the algorithm is the sum of the recursive work (how deep the tree goes and how many leaves it has, which are the base cases) plus the non-recursive work (the computation at each node).
Yes. In some cases, the contribution of Lc is more than the Ic, hence cannot be ignored. Please see the first part of the Master Method video for better understanding.
For example 5, the asymptotic growth rate is ambiguous since we do not know which of the Lc or Ic is growing faster. We will need to use the substitution method to determine the solution.
@@DrMHJamal but on the left sub tree is 1/3 and if we take pivot in middle then right sub tree would be 2/3 so right sub would be bigger if we consider for any value of n, correct? What I thought if not valid then please correct me
@@shivpatel4499 similar thoughts here that we should consider left subtree for Lc , as it would go deeper . Why did you(@Dr. Hasan Jamal) took right one ?
@@parthshingari6082 Right side will go deeper as 2n/3 is great than n/3 and will take more time to reach T(1). To better understand, take a number, say 48, and keep dividing it into 1/3 and 2/3 and see what happens.
i don't understand at example 4 , how the interval node cost at level 1 become 5/16 . Where does the 5 come from . Plz explain it to mw sir, or anyone who has got it.
@@DrMHJamal sir did you mean n^2/4 is 4n^2/16 . It makes it more confusing for me , how can n^2/4 be 4n^2/16. plz explain. because this is the part of the video where i got stuck, and can't move forward.
We are solving for worst-case scenario here, so we are assuming the tree to be full, i.e. all the leaves are at the last level of the tree. So if there are 2 children for a node, it will be the exact power of 2, and if 3 children, it will be the exact power of three and so on. Hope that helps.
This is the best explanation of the recursion tree method on the internet hands down.
best video fr,it think there is no "hard" topics,there are just bad teachers.
This is easily the best explanation on recursion trees that I have ever seen. Thank you so much! :)
I have watched several tutorials on this topic past two hours and this one is by far the best. Finally understand how to solve this type of problems. Thank you!!!
Sir, you are the best. I watched your other video on the master method and now this video, and everything makes sense. You cover so many different examples that it’s enough to fill my understanding of how the problem works, and you explain each thing so well that and slow enough so I can understand. Thank you, I have an exam today and this really helps 🙏
Might be the best video ever on solving recurrences. Thanks you so much sir.
Excellent in delivering concepts..Ma shaa Allah
4 pakka
Your way of teaching is really in depth and covers the max topic... it really gonna help me in my semester exam... I am really grateful and thankful to your hardwork please sir make more n more videos like this....your the only one in this universe who provided this very good topic for free..and in depth..Thank you sir🙏
Greetings from Turkey :) thx for the lectures. they are better than my uni teacher.
I think he is Indian CZcamsr😁😎
He is Pakistani youtuber and a PhD scholar at Comsats University Lahore. Wada aya indian.
@@arslanashraf4379 ha toh kya hua mujhe pata nhi tha
@@technicalspider2547 theek hai koi baat nhi. galti ho jati hai.
He is my uni teacher 😶🤓
There are lot of examples in this. hence it helps to understand the whole problem and concept.
Tysm😊
Best vdo on CZcams for this concept ❤
I Gone Through How many things for this I don't know but get it here thankyou.
amazing video! really helped me understand recursion trees! thanks man
wonderful! This was the best lecture to learn.
It is the best video on Recursive tree method
Absolutely amazing never seen explanation like this
Thank you so much sir. It really helped me understand the recursion tree approach ❤️
Thank you so much sir you are great teacher 👍👍👍
Very well explained, sir 😀. Your explanation is much better than my university professor's.🙃
Life saver! Thank you!
lifesaving tutorial!
Best Explanation Thank You sir !!!!
It was really helpful, Thank you Sir
Sir can you please explain why we are taking the total number of interior nodes as K in the first example and k-1 in the second
The total levels of interior nodes in all examples is K, from level 0 to level k-1. In example 1, since cost at each level is same, we multiply K with n. In example 2, the formula goes from 0 to k-1, which is also K.
Thank you so much. I learned, and enjoyed.
Awesome Bro !
great way of teaching
Hi, why is the depth k and not k+1, for example like a input of n = 32 and we reach a point where we know n/2^k = T(1). so 32/2^5 = 1. However, arent we excluding level 0, meaning the depth should be k+1?. And if we are excluding it, why did you incldue it back again when calculating the total cost starting from level 0 all the way to k-1? Thank you
The depth is indeed k+1 and not k. Level 0 to k-1 are interior nodes, and at kth level, we have leaf nodes.
best explaination
sir is T(1) value assumed to be 1. if not I don't understand Lc, u have just mentioned the number of terms in Lc thank u sir
Yes. T(1) is assumed to be 1. We assume that only one element is left on each leaf node at level 'k'.
Hello Sir. While talkin about the calculation of Lc (Example 1) , you haven't mentioned the cost of a leaf node. Is the cost 1 because T(1) = T(1/2) + 1
At the leaf node, we have only one element which is T(1) = 1.
@@DrMHJamal Also Sir, in Example 4, we only have RST nodes that contributes to the depth. Isn't it true that at the actual kth level only 2 T(1) nodes will be there? So why are we taking 2^k?! After all, the tree isn't a complete binary tree
@@shubhampathak4206 We are working on the worst-case scenario and finding the maximum number of leaves that can exist in the tree. Actually, the total leaves will be less than that. Similarly, Interior nodes will be less at each level than what we are computing, especially deep down the tree. That is why in example 5 we say that the final solution is ambigous. So we are trying to figure out which out of Ic and Lc is the major contributing factor to the total cost. In example 4, it is clear but in example 5 it is not. Hope that helps.
@@DrMHJamal Understood Sir! Thank you so much for your quick replies :)
Superb, Thank you!
i love u sm this made sm sense
Thank your sir
Well explained Dr Jamal thank you
Does any value for n works for the last 2 examples?
Absolutely amazing
i have a doubt in the first example for Ic u have taken K. n but in the second example u have taken sum of all the terms and also u have taken GP of infinite terms
Doubt 1: why did you take infinite terms
Doubt 2: why didn't you take K.N for second example
For doubt 1, see the last slide. For doubt 2, in first example, there are k levels each of cost n making it k.n. In the example 2, each level cost is different so you cannot use k.n. You will have to apply geometric series formula to add the terms.
learned alot sir thank u very much
Thank you 🤲
Hello i have a question. I have read on my book that the recursion tree is used to generate a good guess that is then verified with substitution method. Is it possibile to use the recursion tree alone or do i have to always check the result via mathematical induction?
For some problems, the result is obvious using recursion tree method. For some we need to verify by Substitution method. Like example 5 in the video.
Tqu sir actually solve my problem due to god
Can we say the following: The total work done by the algorithm is the sum of the recursive work (how deep the tree goes and how many leaves it has, which are the base cases) plus the non-recursive work (the computation at each node).
We are calculating non-recursive work at each node of the tree. The recursive work is just function calls which we assume negligible.
@@DrMHJamal Can we say that, the number of leaf nodes is depends on the a and b in the general recurrence relation T(n) = a*T(n/b) + f(n)?
@@DrMHJamal And lastly, can we say that the amount of non-negligible recursive work is reflected to the number of base cases we have?
@@kaankahveci1153 number of leaf nodes is a^k where k is the height of the tree.
@@kaankahveci1153 we don't need to reflect the recursive work. It is negligible.
Would it be a problem if we didn't calculate Lc when calculating the Big O notation?
Yes. In some cases, the contribution of Lc is more than the Ic, hence cannot be ignored. Please see the first part of the Master Method video for better understanding.
Awesome video sir 🙏🙏
sir, why didnt you multiply the cost of leaf node while calculating the Lc? , you just calculated Lc on the basis of total no of leaf nodes..
Our assumption is that the cost of each leaf node is T(1). Meaning there is only one element at individual leaf node.
what if we take theta on example 5 can we say that theta(n. logn)?
please let me know
For example 5, the asymptotic growth rate is ambiguous since we do not know which of the Lc or Ic is growing faster. We will need to use the substitution method to determine the solution.
@@DrMHJamal but on the left sub tree is 1/3 and if we take pivot in middle then right sub tree would be 2/3 so right sub would be bigger if we consider for any value of n, correct? What I thought if not valid then please correct me
@@shivpatel4499 similar thoughts here that we should consider left subtree for Lc , as it would go deeper . Why did you(@Dr. Hasan Jamal) took right one ?
@@parthshingari6082 Right side will go deeper as 2n/3 is great than n/3 and will take more time to reach T(1).
To better understand, take a number, say 48, and keep dividing it into 1/3 and 2/3 and see what happens.
@@shivpatel4499 Correct. That is what is happening in this example.
Great video!
Love you sir ❤
best explanation
Why we can't use (1+1/2+1/4+•••••+1/n)=log n , instead of using geometric series
Because this summation is not equal to log n.
i don't understand at example 4 , how the interval node cost at level 1 become 5/16 . Where does the 5 come from . Plz explain it to mw sir,
or anyone who has got it.
By adding n^2/16 and n^2/4 which is also 4n^2/16.
@@DrMHJamal sir did you mean n^2/4 is 4n^2/16 . It makes it more confusing for me , how can n^2/4 be 4n^2/16. plz explain.
because this is the part of the video where i got stuck, and can't move forward.
@@denzelsmith1961 1/4 = 4/16. Multiply numerator and denominator with 4.
@@DrMHJamal Sir I got u now,
that was a silly confusion. THank you so much.
Sir plz make a video on matrix chain multiplication.😇
very helpful video
What Assumption actually means here? We assume n is exact power of 2 ?
We are solving for worst-case scenario here, so we are assuming the tree to be full, i.e. all the leaves are at the last level of the tree. So if there are 2 children for a node, it will be the exact power of 2, and if 3 children, it will be the exact power of three and so on.
Hope that helps.
@@DrMHJamal please upload more such lectures 🙏
Thankuuuu .......................
big up
❤
You are looking beautiful 😊 may be you already know it, but I just wanna tell you this
24:00 where did that 5 came from?
Add 1/16 and 1/4 (which is also 4/16) and you get 5/16.
Assignment answers
1.n square log n
2.n
3.log log n cube whole square
4.n
5.n log n
For question 3, the answer is 2^n. This is the recurrence equation for the Tower of Hanoi problem.
@@DrMHJamal sir as ka solution bataya da
Sir Kindly isko thora aur achay se samjha detay to acha hota (LIKE USING URDU/HINDI)
sahi keh rha hain ap bhai
Y 5 over 16 in ex 4
Add 1/16 and 1/4 (which is also 4/16) and you get 5/16.
sir can i get this ppt?
✅
hardest way of explaining the concept making the concept super difficult to understand
❤