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
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).
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! 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.
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
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. 😀
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.
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.
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 :)
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.
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?
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!
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)
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).
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)).
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??
![fellow fellow - พรุ่งนี้ไม่มีใครรู้ feat. INK WARUNTORN [OFFICIAL MV]](http://i.ytimg.com/vi/QP6JyjYx_W0/mqdefault.jpg)
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
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.
"nothing very fancy here" i love this line sir!
and really there is nothing very fancy actually......
I find myself smiling after learning this from you, thanks a lot!
same
Ek baar Reddy sir se padh k dekho.
best than any others. good to be teacher of cs
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.
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
Thanks for sharing this! I found it very useful and well explained
best explanation have been reading the Comen book but this is more like the comen book in a video form.
It is very simple, hello from Turkey
Great way of explaining anything....thanks a lot sir😊
❤️❤️ it's amazing
in my class the +cn^2 part
we don't substitute with n ,we keep it as it is for the whole problem
This was very helpful but why did you conclude that it was theta n^2 instead of O n^2?
Shouldn't the root node be n^2?
One of best way to teach this topic👍♥️
Amazing.... In bihari style Garda 😍😍😍😍😍😍😍
Thanku so much finally I understand the whole thing..
ya right it's giving dam deep knowledge.
that was a very good video thanks alot
YOU'RE BREATHTAKING. THANK YOU
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. 😀
Thank you so much!!! Magnificent explanation.
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.
What about floor function? Why did we simply ignore it?
"Let's assume it's not floor, just n/4"
*question ends*
What did we do with it
great explanation sir
Sir your explanation way is awesome!
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 ?
ig it'll not be an ifintie tree becuz somwhere it will be n/2^k =1
OMG You just saved my life sir
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.
Hello Sir, Why it is not theta(n^2 logn_4) ? In merge sort we have nlogn_2
thank you so much. this has helped a TON
Thanks for this bit of information!
thank you so much! pure gold
Why theta tho ?
Good job explaining!!
Will the recurrence tree method always give theta bound, or on which basis have u confirmed that it is. Theeta
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 ?
16^2 doesn't equal 64. I think you mean 4^3
Great Explanation.
you saved my life .thank you
Why did you used theta not Big O?
Thank you so much!
12:20
why you taken theta not big O or omega .
Very helpful.
But why did we find height of tree as we haven't used it....?
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.
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
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
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!
it should be t(n/4) = t(n/4*4) +c(n/4)^2 not c(n/16)^2
Thank you !
one more method is akra bazii method for solving this
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)
8:22 what's the point of the depth
Why not n²/4 in level 1
At level 1 it took cn² the n²/16 at level 2 WHY???
thank you so much
I am not getting the concept how cn^2 time to combine
Sir, which tool u are using to explain this video.
Wacom tablet
Bro you made my day 😍💥
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).
Thank u so much sir 🙏
💯💯💯👍
What is the name of this thing, by which you draw and screen share, record and all stuff???
Ink2Go
Thank you
Thanks sir ji
Shouldn't the answer be (n^2 x logn)
@Neel Rayal I think O(n²) < O(n²logn)
I think 16 sqr = 256 not 64
Its 4^3 not 16^2
Your voice is like rajamouli
why is it 9cn^2/16^2 instead of 9cn^2/64 ??
nevermind LOL
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
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)).
✅
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 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.
Watch at x2
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
did u marry him?
@@MichaelMvano yes i did
@@mazenhachem146 prepare to be poly. i have a final in 5 days