Table of Contents: (and clarifications) Introducing Today's Topic 0:00 - 0:38 Ad 0:38 - 1:11 The Approach We Are Going To Take 1:11 - 2:12 Step #1: Crafting Our Decision Tree Example 2:12 - 7:20 Making Observations About Our Tree 7:20 - 8:58 Step #2: Drawing Our Generalizations 8:58 - 11:50 Step #3: Solving The Relationship 11:50 - 16:48 The Final Solution/Result We Can Bound 16:48 - 17:51 Closing Thoughts 17:51 - 18:36 Clarifications: 10:58 -> I wasn't clear about the n!. We will have n! leaves, at least, because there are n! permutations of the final array. We have to have at least that many terminal states in the decision tree since those are all the possible "final destinations" we can reach through our comparisons. 14:49 -> Correction to what I said: "And...if we add 0 that does nothing for us."
Hey dude, I appreciate the tremendous work that must have gone to make this! You're too awesome man! Thanks a lot, never thought I'll be able to learn this concept as succinctly as you've done.
Can you explain why it is valid to transform a summation of a function calculated with INTEGER indices into an integral (that takes the area under the curve, so it's not only the integer coordinates)?
Thank you for the great video! But can you make a video on similar approach/proof for Comparison based searching using decision trees? I think that would be great to understand too!
Thank you, it is very good that you make checkpoints during the explanation, 'if you get this part you are good'. (Something like this you said if I recall correct).
Hey I really appreciate you efforts but what I know the maximum leaves would be the number of permutations of the array, which is 3! (3 factorial) for three elements. This is because there are six possible ways to arrange three unique elements on the other hand the minimum leaves will be 1 please correct me if I am wrong
I know this is from 2 weeks ago but i'll try anyway. First consider what the leaves actually are. Each leaf represents a sorted list. 1- There has to be at least one leaf that represents each possible list(There can be more than one). 2- Now considering we want to sort 'N' elements, you might know that a list of N elements can be ordered in N! ways or permutations(You can find videos on this if u dont understand how i got N!). So we will have at least N! leaves.
Thanks a lot for class bunkers like me! Anyways, university doesn't teach stuff! They want $$$. Thanks for providing good quality knowledgeable videos!
"...for entertainment reasons" - me: laughing, then realizing that it is way past my study time and that i am actually watching this for entertainment. Great Videos!
I wrote a long response then closed the comment response window....crap. Anyway, it is about the "window" we take the area of. If a function is going up (monotonically increasing) consistently, to get "less" to lower bound we can shift the window to the left. If it is going down (monotonically decreasing) consistently, to get "less" to lower bound we can shift the window to the right. Something along those lines.
Hey! Videos like these help a LOT. Please make some videos on Masters theorem. I think I know the basic intuition behind it, but I'd love to know more. Thanks!
Your videos are so good. I have studied algorithms for a while now, and I finally found your channel! I have used so much time on bad videos and explanations, but this is great. I think the reason for why I havent found any of your videos before is because of the titles. When Im looking for something I usually just type e.g. "Dijkstra", and yours are so long. Little tip maybe.
Sorry, but I am still getting confused as to why the maximum amount of leaves would be 8. Would it just be the individual elements that make up for the external leaves at the end of the last comparison? I might have just missed something, but other than that this video was very helpful!!
I have two doubts: 1. # of comparisons is O(2^h) but you just showed h >= O(n log n), but h is not the final answer. 2. You change the discrete summation into an integral, that doesn't seem to make sense. Integral is the area under curve and it is the limit of sum when the step goes to 0, but there is no concept of limit whatsoever in your equation
@@renyuanzhang9706 I think you mean Ω, not O. :) 1. The number of comparisons is h. - You do not visit the whole tree to order your array. At each node it is either "". Both cases cannot appear for the same input. So the number of comparisons is the height of the tree. 2. He does not explain it. But if you compute runtime for Ω you actually use the limit. That is the known definition. Ω(f(n)) ≥ { g(n) : there exists c > 0 and n0 such that g(n) ≤ c.f(n) for all n > n0. } The inequation must hold for all n > n0. That is your limit.
g(n) = O(f(n)) if there is a constant c > 0 and a n0 such that c * f(n) > g(n) if n >= n0 So we have to show that c * n * log n > log n! for any n > n0 That is quite simple because n * log n = log (n^n) and n^n obviously is equal to or bigger than n! for any n above 0.
I am watching this video to better understand the logic behind omega(n log n), then he said "IT'S FOR ENTERTAINMENT PURPOSES", I have never felt any smarter in my life 😂😂😂
Well, as a mathematician I cannot ignore a few mistakes that you made. Firstly, you cannot just say that integral is equal to the sum. In this case, it is true, but in general, it is false. I remember watched interesting proof for this integral. If I will find it, I will attach it in the comment. Secondly, distribution on the 15th minute is incorrect. The base of the log should be 2, not e. In general, it was an interesting video, but you should not break your explanation, because it breaks the focus.
Hey i just stumbled upon your channel "really lucky" and i gotta say your style is very unique and clear any tips bro to learn data structures online too?
i was looking at this playlist but i am not sure if its enough? for example it doesn't cover nodes? excuse my ignorance ruclips.net/video/Zc54gFhdpLA/видео.html
Why can't my teachers show enthusiasm like this, I mean their lectures are fine and the explanations are OK, but they do it in a very mechanical way that I start day dreaming 5 minutes after the lecture starts. Anyways, great job brother.
Hahahaha, because: 1.) Most of the time it is me half lying because I haven't done it myself or I don't understand it. 2.) It would alienate half the audience who as soon as they see a summation or constructive induction will tune out 3.) It would increase prep and production time since once you make a video, it is permanent. A math mistake can't be "erased over" in video format so great care must be taken to make sure everything is right. In this video's case (and I remember doing it) I had all of the equations. I probably said this due to #2.
I am curious if we can create "quaternary search" that would be using the && operator or "or" operator..in terms of big O it is log base 4 to the power of n. And then "tertiary search",up until "10th search"
Hey. I'm not a Comp Sci student; I've only looked up sorting algorithms on RUclips vids(especially MITOpenCourseware) so am not an expert but think I can weigh in here. Please correct me if I'm wrong. I thought the lower bound omega [Ω()] is the time it takes for the algo to finish sorting the best case input values i.e. the time to sort if you're really lucky with the array you're given. That would be the shortest possible depth of a leaf (e.g. on the leftmost branch of your diagram that compares A[1] to A[2], A[2] to A[3], A[3] to A[4], etc) which is n (in the best case of having an already sorted list) I say MINIMUM DEPTH of leaf/node as opposed to minimum number of leaves because only 'depth' number of comparisons are done one that branch. Some sources I checked were Wikipedia & GeeksforGeeks for best-case time where asymptotically sub-optimal algorithms like insertionsort & bubblesort actually have Ω(n) en.wikipedia.org/wiki/Sorting_algorithm www.geeksforgeeks.org/time-complexities-of-all-sorting-algorithms/ Please let me know what you think, I'm doing some coursework on the subject and am preparing for interviews so look forward to seeing more of your videos. Thanks
Hey I don't remember much from this video to be honest - I knew this pretty well when I recorded this so recorded me should be trusted above current me
Heap Sort has O(n log(n)) complexity :) "I thought the lower bound omega [Ω()] is the time it takes for the algo to finish sorting the best case input values..." --> Be careful, complexity analysis is used to compute the runtime for different cases. (Best, Average, Worst) Normally people mean the Worst Case when they talk about runtime. Here that was the case. :D
Dude, You are just awesome. I've been following you for a while now and I'm really motivated from you. One question though: how did you learn maths? And I would be really happy if you can make a video on your journey to becoming a pro at algos and programming.
Hahahaha, I'm not a "pro". I am a normal student. I'm going into my 3rd year at the University of Maryland College Park and this is just standard stuff you do in algorithms. None of it is me making novel discoveries. I just explain what I learn.
@@BackToBackSWE (^_^), How do I start learning? Same here, I too am going to my 3rd year now. My university sucks! what would be your strategy to nail down big companies interviews in my next two years, I would really appreciate your suggestions, thank!
@@rahil_rehan Haha. Do a lot of Leetcode and deeply understand everything on this channel. That's basically what the interviews are about...algos and data structures. There is no "path". It depends on what you are good and bad at. That is for you to self-assess. But then just work on those things.
![FendiDa Rappa - Clock Dat ft. Shamar Marco [Official Music Video]](http://i.ytimg.com/vi/3NBU8KHdxYY/mqdefault.jpg)
Table of Contents: (and clarifications)
Introducing Today's Topic 0:00 - 0:38
Ad 0:38 - 1:11
The Approach We Are Going To Take 1:11 - 2:12
Step #1: Crafting Our Decision Tree Example 2:12 - 7:20
Making Observations About Our Tree 7:20 - 8:58
Step #2: Drawing Our Generalizations 8:58 - 11:50
Step #3: Solving The Relationship 11:50 - 16:48
The Final Solution/Result We Can Bound 16:48 - 17:51
Closing Thoughts 17:51 - 18:36
Clarifications:
10:58 -> I wasn't clear about the n!. We will have n! leaves, at least, because there are n! permutations of the final array. We have to have at least that many terminal states in the decision tree since those are all the possible "final destinations" we can reach through our comparisons.
14:49 -> Correction to what I said: "And...if we add 0 that does nothing for us."
*You are awesome.*
Hey ben, could you say what's the name of this music? As good as you teach, the music at the end touches the heart
I've never thought that i would watch such videos for their entertainment value. But here I am, enjoying the neatly prepeared math.
nice
Hey dude, I appreciate the tremendous work that must have gone to make this! You're too awesome man! Thanks a lot, never thought I'll be able to learn this concept as succinctly as you've done.
thanks
Thank you so much for your videos ❤️ I got an offer from Amazon! 😀
Ay. Nice. Enjoy your time there, wish you a happy future.
congrats man!
Your attitude makes reviewing algorithms fun, thanks for the good vibes.
ye
Simple Mathematical Explanation for a complex case
Thanks a lot man. i was struggling a lot to understand it. its clear now
Can you explain why it is valid to transform a summation of a function calculated with INTEGER indices into an integral (that takes the area under the curve, so it's not only the integer coordinates)?
I don't remember the math or the approach to be honest, I'd have to rewatch the video to remember
@@BackToBackSWE Thank you very much for the honest answer!
Thank you so much, I finally understand so many fuzzy concepts because of you
Happy Holidays! Really glad to help 🎉 Do you know about the 5 Day Free Mini Course? Check it out here - backtobackswe.com/
Thank you for the great video! But can you make a video on similar approach/proof for Comparison based searching using decision trees? I think that would be great to understand too!
Thank you, it is very good that you make checkpoints during the explanation, 'if you get this part you are good'. (Something like this you said if I recall correct).
ok
bruh.. you just cleared up a semesters worth of confusion
Hey I really appreciate you efforts but what I know the maximum leaves would be the number of permutations of the array, which is 3! (3 factorial) for three elements. This is because there are six possible ways to arrange three unique elements on the other hand the minimum leaves will be 1 please correct me if I am wrong
Your videos are awesome! Also did a recent video about a silicon Valley salary analysis get taken down or something? Or am I seeing things
Thanks, means a lot. Yeah, I fucked that video up. I have a new one I shot this morning that I'll post later today.
We learned this exact thing in class the other day... I was so confused and now I get it! Thanks so much! :) - UBC Comp Sci
nice
14:48 I think you mean "if we add 0, that does nothing for us"?
yeah, I addressed that in the table of contents thingy
I cant get the minimum no. of leaves. How is that n!
I remember no concrete information from this video.
I know this is from 2 weeks ago but i'll try anyway.
First consider what the leaves actually are. Each leaf represents a sorted list.
1- There has to be at least one leaf that represents each possible list(There can be more than one).
2- Now considering we want to sort 'N' elements, you might know that a list of N elements can be ordered in N! ways or permutations(You can find videos on this if u dont understand how i got N!).
So we will have at least N! leaves.
Thanks a lot for class bunkers like me! Anyways, university doesn't teach stuff! They want $$$. Thanks for providing good quality knowledgeable videos!
ye
This was cool! I’d love to see more of these.
Eh, I think these are boring to be honest. I wanna start making more videos that are more..."me"....you'll see what I mean.
Hey man, I really enjoyed the video and your energy. You kept the video so interesting and I really appreciate what you're doing. Subscribed!
"...for entertainment reasons" - me: laughing, then realizing that it is way past my study time and that i am actually watching this for entertainment. Great Videos!
nice lol
Excellent explanation, thank you
Thank you, glad you liked it 😀
Do check out backtobackswe.com/platform/content
and please recommend us to your family and friends 😀
Superb, but i have a question why taking the integral from 2 to n gives us the minimum bound?
I wrote a long response then closed the comment response window....crap. Anyway, it is about the "window" we take the area of.
If a function is going up (monotonically increasing) consistently, to get "less" to lower bound we can shift the window to the left. If it is going down (monotonically decreasing) consistently, to get "less" to lower bound we can shift the window to the right.
Something along those lines.
Hey! Videos like these help a LOT. Please make some videos on Masters theorem. I think I know the basic intuition behind it, but I'd love to know more. Thanks!
I'm making a website around this, it is pretty cool. You'll see it in 2-3 months.
@@BackToBackSWEAwesome!
@@Finn-jp6pn Working on it rn. In the dark. :)
@@BackToBackSWE haha...it's morning here, and I'm preparing for tomorrow's DSA exam. Your videos are a great help. Good luck with your website 👍
Your videos are so good. I have studied algorithms for a while now, and I finally found your channel! I have used so much time on bad videos and explanations, but this is great. I think the reason for why I havent found any of your videos before is because of the titles. When Im looking for something I usually just type e.g. "Dijkstra", and yours are so long. Little tip maybe.
Thanks
Sorry, but I am still getting confused as to why the maximum amount of leaves would be 8. Would it just be the individual elements that make up for the external leaves at the end of the last comparison? I might have just missed something, but other than that this video was very helpful!!
This is amazing, you are much better than our professer:)
please keep doing it!
no, I'm a lot dumber
I have two doubts: 1. # of comparisons is O(2^h) but you just showed h >= O(n log n), but h is not the final answer. 2. You change the discrete summation into an integral, that doesn't seem to make sense. Integral is the area under curve and it is the limit of sum when the step goes to 0, but there is no concept of limit whatsoever in your equation
I dont remember the math I'm sorry - rapid replying to comments
@@BackToBackSWE How about the first question? Is the number of comparison 2^h or h?
@@renyuanzhang9706 I think you mean Ω, not O. :)
1. The number of comparisons is h. - You do not visit the whole tree to order your array. At each node it is either "". Both cases cannot appear for the same input. So the number of comparisons is the height of the tree.
2. He does not explain it. But if you compute runtime for Ω you actually use the limit. That is the known definition.
Ω(f(n)) ≥ { g(n) : there exists c > 0 and n0 such that g(n) ≤ c.f(n) for all n > n0. }
The inequation must hold for all n > n0. That is your limit.
g(n) = O(f(n)) if there is a constant c > 0 and a n0 such that c * f(n) > g(n) if n >= n0
So we have to show that c * n * log n > log n! for any n > n0
That is quite simple because n * log n = log (n^n) and n^n obviously is equal to or bigger than n! for any n above 0.
I am watching this video to better understand the logic behind omega(n log n), then he said "IT'S FOR ENTERTAINMENT PURPOSES", I have never felt any smarter in my life 😂😂😂
Very Nice !!!!!!!!!!!!!!! Thanks
sure
Well, as a mathematician I cannot ignore a few mistakes that you made.
Firstly, you cannot just say that integral is equal to the sum. In this case, it is true, but in general, it is false. I remember watched interesting proof for this integral. If I will find it, I will attach it in the comment.
Secondly, distribution on the 15th minute is incorrect. The base of the log should be 2, not e.
In general, it was an interesting video, but you should not break your explanation, because it breaks the focus.
this is so good. not good it's great. thank you for such amazing video
sure
Excellent explanation ! Thank you so much sir ....
sure.
The best way of teaching complexities.Thank you 😊😊
sure
Hey i just stumbled upon your channel "really lucky" and i gotta say your style is very unique and clear
any tips bro to learn data structures online too?
i was looking at this playlist but i am not sure if its enough? for example it doesn't cover nodes? excuse my ignorance
ruclips.net/video/Zc54gFhdpLA/видео.html
I have not many tips except practice a lot.
I just decided to like every video you have :) Great content
nice
teacher dif my teacher rambling while you make connections and connect the dot now my note they shine !!
Thank you! Video was amazing and you explained the concept very well!
thanks
The best explanation ever heard... great job.
thanks
Love the way you simplify things 💕
Why can't my teachers show enthusiasm like this, I mean their lectures are fine and the explanations are OK, but they do it in a very mechanical way that I start day dreaming 5 minutes after the lecture starts. Anyways, great job brother.
Thank you, glad you liked it 😀
Do check out backtobackswe.com/platform/content
and please recommend us to your family and friends 😀
outro had me staring off into the night sky thinking about my place in the universe
Im kind of shocked that people consider this level of math complicated......
think of the amount of effort and research he had done to put all this together ...... thanks a lot ,subscribed :)
yes
This is what I am trying to do
n also the log n of big O notation relationship
Are you going to take Design and Analysis of Algorithms?
is that 451?
Yup!
That was simple and understandable. Thank you!
Why are you so afraid of showing the Math ! You don't need to tell "dont worry about the math" Everytime you do some Math!
Hahahaha, because:
1.) Most of the time it is me half lying because I haven't done it myself or I don't understand it.
2.) It would alienate half the audience who as soon as they see a summation or constructive induction will tune out
3.) It would increase prep and production time since once you make a video, it is permanent. A math mistake can't be "erased over" in video format so great care must be taken to make sure everything is right.
In this video's case (and I remember doing it) I had all of the equations. I probably said this due to #2.
@@BackToBackSWE Haha. Fair Enough. Good video. keep up the good work! :)
I am curious if we can create "quaternary search" that would be using the && operator or "or" operator..in terms of big O it is log base 4 to the power of n.
And then "tertiary search",up until "10th search"
oh my god I love you! thank you very much.
I just found a new internet tutor :)
ye
You are amazing man ❤🔥❤❤
i just about to finish my first year at computer science thanks to you, your videos are the best
great! keep it up!!! a great field to be in
this helped me out man. Thanks for the tremendous work you did there. each part was beautifully explained.
would please cover segment tree algorithm implentation too??
sure
Perfect 👌🏽 explanation
ye
Love the ending. Thanks for explaining, nowhere i looked explained it with enough detail and simplicity as you. Thanks!
if interview > my_math_skill : return jokes
ok
amazing explaination , love , love , love
Hey. I'm not a Comp Sci student; I've only looked up sorting algorithms on RUclips vids(especially MITOpenCourseware) so am not an expert but think I can weigh in here. Please correct me if I'm wrong.
I thought the lower bound omega [Ω()] is the time it takes for the algo to finish sorting the best case input values i.e. the time to sort if you're really lucky with the array you're given. That would be the shortest possible depth of a leaf (e.g. on the leftmost branch of your diagram that compares A[1] to A[2], A[2] to A[3], A[3] to A[4], etc) which is n (in the best case of having an already sorted list)
I say MINIMUM DEPTH of leaf/node as opposed to minimum number of leaves because only 'depth' number of comparisons are done one that branch.
Some sources I checked were Wikipedia & GeeksforGeeks for best-case time where asymptotically sub-optimal algorithms like insertionsort & bubblesort actually have Ω(n)
en.wikipedia.org/wiki/Sorting_algorithm
www.geeksforgeeks.org/time-complexities-of-all-sorting-algorithms/
Please let me know what you think, I'm doing some coursework on the subject and am preparing for interviews so look forward to seeing more of your videos. Thanks
Hey I don't remember much from this video to be honest - I knew this pretty well when I recorded this so recorded me should be trusted above current me
Heap Sort has O(n log(n)) complexity :)
"I thought the lower bound omega [Ω()] is the time it takes for the algo to finish sorting the best case input values..."
--> Be careful, complexity analysis is used to compute the runtime for different cases. (Best, Average, Worst) Normally people mean the Worst Case when they talk about runtime. Here that was the case. :D
thanks a lot，great lesson!😃
the website is out now right ?
Thank u
sure
It’s “number”, not “ amount”
ok
just wow. thanks man
Perfect explanation
finally a neat explanation for this point, thanks a lot 💕
thanks bro.
Cool explanation
Gold
always loved the way you teach !! Starting from beginning
ye
A,B,C,D,doit
Great job
thx
thank you so much! just like a magic，i need to watch once again.
haha nice
支持一下
谢谢！
this channel doesnt have a potential but is a potential seriously quality content
what haha
Thanks so much!
Cool
hey
Dude, You are just awesome. I've been following you for a while now and I'm really motivated from you. One question though: how did you learn maths?
And I would be really happy if you can make a video on your journey to becoming a pro at algos and programming.
Hahahaha, I'm not a "pro". I am a normal student. I'm going into my 3rd year at the University of Maryland College Park and this is just standard stuff you do in algorithms. None of it is me making novel discoveries. I just explain what I learn.
@@BackToBackSWE (^_^), How do I start learning?
Same here, I too am going to my 3rd year now. My university sucks! what would be your strategy to nail down big companies interviews in my next two years, I would really appreciate your suggestions, thank!
@@rahil_rehan Haha. Do a lot of Leetcode and deeply understand everything on this channel. That's basically what the interviews are about...algos and data structures.
There is no "path". It depends on what you are good and bad at. That is for you to self-assess. But then just work on those things.
finally, updated again. ha
hey