Recursion tree method | Solving Recurrences | Data Structure & Algorithm | Gate Applied Course
Вставка
- Опубліковано 6 жов 2024
- #gatecse #ds #algorithm #recursiontree #recurrences #appliedgate #gate2022
Subject Name: Data Structures and Algorithms
Chapter Name: Solving Recurrences
Topic Name: Recursion Tree
Please visit: gate.appliedro..., interviewprep....
For any queries you can either drop a mail to gatecse@appliedroots.com or call us at +91 844-844-0102
Refer: en.wikipedia.o...
The best teachers are the passionate ones. Thanks for the contribution
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
I find myself smiling after learning this from you, thanks a lot!
same
Ek baar Reddy sir se padh k dekho.
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).
Nice. Just went over this in class and you explained it better in a fraction of the time. Appreciate the work!
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.
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
"nothing very fancy here" i love this line sir!
and really there is nothing very fancy actually......
The best explanation I have ever witnessed.......hats off🙏
Kuch bhi ? master method is easy peasy.
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.
best than any others. good to be teacher of cs
best explanation have been reading the Comen book but this is more like the comen book in a video form.
Thanks for sharing this! I found it very useful and well explained
"Let's assume it's not floor, just n/4"
*question ends*
What did we do with it
Great way of explaining anything....thanks a lot sir😊
❤️❤️ it's amazing
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.
Shouldn't the root node be 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
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 was very helpful but why did you conclude that it was theta n^2 instead of O n^2?
It is very simple, hello from Turkey
Thanku so much finally I understand the whole thing..
ya right it's giving dam deep knowledge.
One of best way to teach this topic👍♥️
YOU'RE BREATHTAKING. THANK YOU
Thank you so much!!! Magnificent explanation.
Sir your explanation way is awesome!
thank you so much. this has helped a TON
why you taken theta not big O or omega .
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.
What about floor function? Why did we simply ignore it?
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 ?
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.
16^2 doesn't equal 64. I think you mean 4^3
that was a very good video thanks alot
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!
Why theta tho ?
OMG You just saved my life sir
thank you so much! pure gold
Why did you used theta not Big O?
But why did we find height of tree as we haven't used it....?
Thanks for this bit of information!
great explanation sir
Will the recurrence tree method always give theta bound, or on which basis have u confirmed that it is. Theeta
it should be t(n/4) = t(n/4*4) +c(n/4)^2 not c(n/16)^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 ?
Hello Sir, Why it is not theta(n^2 logn_4) ? In merge sort we have nlogn_2
you saved my life .thank you
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.
Sir why we use theta here instead of other notations
Thank you so much!
Great Explanation.
At level 1 it took cn² the n²/16 at level 2 WHY???
I think 16 sqr = 256 not 64
Its 4^3 not 16^2
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
Good job explaining!!
Thank you !
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)
Amazing.... In bihari style Garda 😍😍😍😍😍😍😍
Shouldn't the answer be (n^2 x logn)
@Neel Rayal I think O(n²) < O(n²logn)
Very helpful.
I am not getting the concept how cn^2 time to combine
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).
one more method is akra bazii method for solving this
Sir, which tool u are using to explain this video.
Wacom tablet
8:22 what's the point of the depth
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?
What is the name of this thing, by which you draw and screen share, record and all stuff???
Ink2Go
Bro you made my day 😍💥
Why not n²/4 in level 1
12:20
thank you so much
Thank u so much sir 🙏
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
Thank you
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)
Thanks sir ji
why is it 9cn^2/16^2 instead of 9cn^2/64 ??
nevermind LOL
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.
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)).
Your voice is like rajamouli
💯💯💯👍
✅
Watch at x2
IF I PASS MY FINAL TMRW IM GONNA MARRY YOU
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.