Recursion tree method | Solving Recurrences | Data Structure & Algorithm | Gate Applied Course
HTML-код
- Опубликовано: 7 май 2019
- #gatecse #ds #algorithm #recursiontree #recurrences #appliedgate #gate2022
Subject Name: Data Structures and Algorithms
Chapter Name: Solving Recurrences
Topic Name: Recursion Tree
Please visit: gate.appliedroots.com/, interviewprep.appliedroots.com
For any queries you can either drop a mail to gatecse@appliedroots.com or call us at +91 844-844-0102
Refer: en.wikipedia.org/wiki/Geometr...
The best teachers are the passionate ones. Thanks for the contribution
Nice. Just went over this in class and you explained it better in a fraction of the time. Appreciate the work!
"nothing very fancy here" i love this line sir!
and really there is nothing very fancy actually......
best than any others. good to be teacher of cs
YOU'RE BREATHTAKING. THANK YOU
Thanks for sharing this! I found it very useful and well explained
I find myself smiling after learning this from you, thanks a lot!
same
Ek baar Reddy sir se padh k dekho.
cn^2 is the time that takes to 'merge' the subproblems. And that is why T(n/4) = 3T(n/16) + c(n/4)^2 takes for each 3 subproblems c(n/4)^2 times 3 ===> 3/16 * cn^2.
Thank you so much!!! Magnificent explanation.
I have some doubts as follows:
1. why we have not included log4n, and the final result would be n^2 log4n
2. The series should start from 3n/4 , 9n/16, .... so on, so in that case formula should change
3. why we have considered infinite series and why not finite(n) series?
because this picture is missing a little bit of data, at node one as you can easily see we start at n/4. thus T(n/4) = (n/4)^2. (we get this from the n^2 term) this represents the first step whilst it shows and looks like 3n/4 it's actually 3T(n/4) so do the math
at the first part of this tree n/16 + n/16 + n/16 = 3n/16
next step is T(n/16) this results in (3n/16)^2 = 9n/16^2
this gives us the sum formula of (3/16)^i * n^2 *c
once again look at the tree
n/4 n/4 n/4
n/16 n/16 n/16 n/16 n/16 n/16 n/16 n/16 n/16
what's implied is:
(n/4)^2 + (n/4)^2 + (n/4)^2 = 3n/16 at step one
=(n/16)^2 + (n/16)^2 + (n/16)^2 , (n/16)^2 + (n/16)^2 + (n/16)^2 , (n/16)^2 + (n/16)^2 + (n/16)^2
again the reason you square is because the function seems to be order of n^2
at step two this results in: (3/16)^2 = total of 9 n^2 / 256
at next step: (3/16)^3
so on and so forth you get the idea (3/16)^n
your confusion as well as mine initially must be from the part where he shouws step one with n/4 *cn^2
the right side should say 3/16*cn^2
and the step two where he has n/16*cn^2 should say (3/16)^2*cn^2
Based on my textbook and explanations from my professor, I think you're right and that this video is incorrect.
You mean 3 times (n^2)/16. And so on
Thanks for this bit of information!
One of best way to teach this topic👍♥️
Thank you! I couldn't understand it in other people's videos, but this was very descriptive. You have a logic-based approach that is far from memorized.
The best explanation I have ever witnessed.......hats off🙏
Kuch bhi ? master method is easy peasy.
thank you so much. this has helped a TON
In the geometric series, there are exactly log n base 4 terms. So why do we use infinite series formula here? Why not use the formula, Sum = a^m(r^m - 1)/(r+1), where m = number of terms in GP = log n base 4 in this example.
I think it is a simplification to get rid of the log_4(n) factor in the exponent of the result you get when you use the geometric sum formula.
It is just a way to bound it (from above).
thank you so much! pure gold
Sir your explanation way is awesome!
Great Explanation.
you saved my life .thank you
best explanation have been reading the Comen book but this is more like the comen book in a video form.
Good job explaining!!
Great way of explaining anything....thanks a lot sir😊
❤️❤️ it's amazing
that was a very good video thanks alot
OMG You just saved my life sir
great explanation sir
Bro you made my day 😍💥
Thank you so much!
Very helpful.
It is very simple, hello from Turkey
Thanks sir ji
Thank u so much sir 🙏
Shouldn't the root node be n^2?
Thank you !
Thanku so much finally I understand the whole thing..
ya right it's giving dam deep knowledge.
it is so nice thanks but i confused why you did not chosen the root cn square because you chose the root to be n only ?
This was very helpful but why did you conclude that it was theta n^2 instead of O n^2?
in my class the +cn^2 part
we don't substitute with n ,we keep it as it is for the whole problem
thank you so much
For those who have not convinced here is the my ans c.n^2(gp of 3/16 goes k times ). So waht is k here ? K= logn base 4 there for GP becomes c.n^2((3/16)^logn + constant ) as n goes to infinity 3/16 vanished or becomes close to zero
k is the depth of the tree and the geometric series which we get is the end until it becomes one so we considered that it is till infinity there is a difference bro
What about floor function? Why did we simply ignore it?
Thank you
Amazing.... In bihari style Garda 😍😍😍😍😍😍😍
Will the recurrence tree method always give theta bound, or on which basis have u confirmed that it is. Theeta
Hello Sir, Why it is not theta(n^2 logn_4) ? In merge sort we have nlogn_2
Thank you so much, this was super helpful
Glad it was helpful!
@@GATEAppliedCourse sir why it is theta of n^2 why not big O ?
Why did you used theta not Big O?
why you taken theta not big O or omega .
Sir why we use theta here instead of other notations
Why theta tho ?
I am not getting the concept how cn^2 time to combine
But why did we find height of tree as we haven't used it....?
But you ignored the floor function in this question . Will the answer still be the same if you consider the floor function ? If not, what changes have to be done ?
Great explanation though .
answer still same, the reason you floor it is to account for odd number n's so its a fine technical detail that gets lost in the big O notation. I wish i understood it well enough to explain but I dont so trust me, you can ignore all floor and cieling notations here.
"Let's assume it's not floor, just n/4"
*question ends*
What did we do with it
ig it'll not be an ifintie tree becuz somwhere it will be n/2^k =1
how does the depth of the tree comes into play for this particular equation??
THIS IS A GUESS BY A CLUELESS ALGORITHMS STUDENT: I think it was disregarded because the growth rate provided by the depth is less than the growth rate provided by the series summation. If anyone has a better answer please reply because I'm worried about my midterm coming up!
actually here we assumed that series is infinite but what happens really is that we go till the height of the tree. But it is very hard to solve so we assume this as an infinite gp. 😀
This is not a infinite sum to use the formula a/(1-r) , did you use it as infinite series considering infinity to be upper bound??
For time complexity, we always consider large input size. So n is large here. So no of terms log(n) base 3 is also large. So there are large no of terms(almost infinite for large n).
12:20
8:22 what's the point of the depth
Why not n²/4 in level 1
How do you combine [n/64, n/64, n/64] into n/16^2?
In the recurrence relation: cn^2 is nothing but the time taken to combine the divided parts into one.
Now if we look at this part where each problem was divided into n/64. When we put n = n/16 we get from the recurrence equation that each part of the n/16th sub problem is divided into (1/16)*(n/4) i.e. n/64. Further we require c*(n/64)^2 (i.e. after putting n = n/16) time to convert these n/64 sub problems into n/16 problem.
hope it helps. If not reply.
At level 1 it took cn² the n²/16 at level 2 WHY???
this problem is straight from introduction to algorithms edition three page 89.
Yes, it is. This course is based heavily on Introduction to Algorithms by CLRS as we mentioned at the at the very beginning of this course.
💯💯💯👍
One question if we are given T(n) = 8/6T(6n/7) + 7/6T(n/7) + cn then how to draw the tree
It's been 5 months, but answering it for others... In this we exclude the time complexity due to 7/6T(n/7) as time consumed is less compared to 8/6T(6n/7). So the final answer will include the time complexity due to 8/6T(6n/7)
Sir, which tool u are using to explain this video.
Wacom tablet
On 4:15 We are dividing it into 3 parts but on merging of these the part we are not getting it as full......
n/4+n/4+n/4=3n/4 which is not equal to n...... Is not a problem? I am getting confusion can you plz tell me what is it?
same
Whatever an actual algorithm does which implements this recursion: the "missing" part is obiously not needed anymore for the solution. A quarter gets *removed* so to say because it is irrelevant to what the algorithm is doing. The sum of the subproblems must not be equal to n. The equation tells you, what value T(n) is going to have if you insert n into function T (T(n) is a notation for: Function T applied on value n). Think of it like any other function f: X->Y with f(x) = y. x is not nessecarily equal to y, but the function f applied on x is exactly y!
16^2 doesn't equal 64. I think you mean 4^3
What is the name of this thing, by which you draw and screen share, record and all stuff???
Ink2Go
✅
it should be t(n/4) = t(n/4*4) +c(n/4)^2 not c(n/16)^2
one more method is akra bazii method for solving this
why is it 9cn^2/16^2 instead of 9cn^2/64 ??
nevermind LOL
You forgot to multiply it with the height log4n. so the answer should be O(n^2 log4n). Am I wrong?
Yes you're wrong. He added the terms at each level manually into a series so there's no point in multiplying with log4(n).
For example if you have to add 1,2,3,4 ; after doing 1+2+3+4, you don't need to multiply it with the number of terms.
But series is not infinite😕 how can we use 1/1-r
suppose that a(n) is a geometric serial with constant "r" , we use S(n) = a(1).(1 - r^n)/(1 -r)
why theta not big O? at end.
You can also use big O instead of theta. If something is both O(n) and theta(n) it means its an asyptotically tight bound, which is the goal when finding a bound. If its not clear what I mean, consider this: everything that is O(n) is also O(n^2) and O(n^3) and O(n^4) and everything that is asymptotically larger than O(n), but O(n) is the bound you choose because it is the closest bound to the function at hand. How do you know if your bound is the closest? It will have the same theta and big O bound (in my example, that would be O(n) and theta(n)).
My professor would only say: On this step, if you don't know what to do, go back and review your calculus I material XDDDDDDDDDDDDDDDDDDDDDD
Your voice is like rajamouli
Why is the summation carried out till infinity when we know that it goes till log4(n)?
n might be infinite though, right?
its a convergent series.A convergent series may have an infinite number of terms but will always converge to a finite value.
I think 16 sqr = 256 not 64
Its 4^3 not 16^2
Watch at x2
how does n/4 + n/4 + n/4 = cn^2. until this is clear....nothing in the rest of this video makes any sense. i think that is where this video is failing to teach. thanks for the effort though. i have to find another resource though.
he never says it's equal to cn²! He says the problem of n is broken into three parts of size n/4 PLUS cn²! It's right there in the equation and he keeps saying our three-part subproblems must be *combined with* cn². If you do not listen closely enough you'll have problems with other resources as well! ;)
@@Kirmeins its very nice and respectful of you to explain him, answer him and help him clear his doubts. But your reply was a little abrasive.
cn^2 is the time that takes to 'merge' the subproblems. And that is why T(n/4) = 3T(n/16) + c(n/4)^2 takes for each 3 subproblems c(n/4)^2 times 3 ===> 3/16 * cn^2.
Shouldn't the answer be (n^2 x logn)
@Neel Rayal I think O(n²) < O(n²logn)
Sir please solve this. Problem
T(n)=2T(n-1)+T(n/2)+n
Using recursion tree method
Have you taken this question from any sources? I am wondering How can I break a problem of n into 2 problems of size (n-1) each recursivly and again n/2 ? and combine it with O(n) time??
imagine you have an array of size 4 and now according to your recurrence equation, it will be divided in 3,3,2 Can this be a case?
IF I PASS MY FINAL TMRW IM GONNA MARRY YOU
Very good video! Helping me for studying for my midterm tomorrow tremendously. What software are you guys using to draw like that with the toolbar on the bottom? Thanks again :)
same here