Це відео не доступне.
Перепрошуємо.
Why Comparison Based Sorting Algorithms Are Ω(n*lg(n))
Вставка
- Опубліковано 17 сер 2024
- Free 5-Day Mini-Course: backtobackswe.com
Try Our Full Platform: backtobackswe....
📹 Intuitive Video Explanations
🏃 Run Code As You Learn
💾 Save Progress
❓New Unseen Questions
🔎 Get All Solutions
I found this proof in my algorithms class notes. I think I explained this decently.
Some Notes On This Topic: www.cs.umd.edu...
++++++++++++++++++++++++++++++++++++++++++++++++++
HackerRank: / @hackerrankofficial
Tuschar Roy: / tusharroy2525
GeeksForGeeks: / @geeksforgeeksvideos
Jarvis Johnson: / vsympathyv
Success In Tech: / @successintech
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
Your attitude makes reviewing algorithms fun, thanks for the good vibes.
ye
bruh.. you just cleared up a semesters worth of confusion
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!
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, 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
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
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
Love the ending. Thanks for explaining, nowhere i looked explained it with enough detail and simplicity as you. Thanks!
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!
outro had me staring off into the night sky thinking about my place in the universe
think of the amount of effort and research he had done to put all this together ...... thanks a lot ,subscribed :)
yes
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 👍
teacher dif my teacher rambling while you make connections and connect the dot now my note they shine !!
this helped me out man. Thanks for the tremendous work you did there. each part was beautifully explained.
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!
"...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
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.
Simple Mathematical Explanation for a complex case
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
Thanks a lot man. i was struggling a lot to understand it. its clear now
The best way of teaching complexities.Thank you 😊😊
sure
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 😀
This is amazing, you are much better than our professer:)
please keep doing it!
no, I'm a lot dumber
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!
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
Thank you! Video was amazing and you explained the concept very well!
thanks
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
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/
Love the way you simplify things 💕
I just decided to like every video you have :) Great content
nice
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
ua-cam.com/video/Zc54gFhdpLA/v-deo.html
I have not many tips except practice a lot.
The best explanation ever heard... great job.
thanks
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.
This is what I am trying to do
n also the log n of big O notation relationship
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.
That was simple and understandable. Thank you!
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.
Excellent explanation ! Thank you so much sir ....
sure.
always loved the way you teach !! Starting from beginning
ye
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.
finally a neat explanation for this point, thanks a lot 💕
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 UA-cam 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.
the website is out now right ?
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 😂😂😂
this channel doesnt have a potential but is a potential seriously quality content
what haha
oh my god I love you! thank you very much.
I just found a new internet tutor :)
ye
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 😀
would please cover segment tree algorithm implentation too??
sure
amazing explaination , love , love , love
thanks a lot，great lesson!😃
Perfect explanation
this is so good. not good it's great. thank you for such amazing video
sure
Are you going to take Design and Analysis of Algorithms?
is that 451?
Yup!
Perfect 👌🏽 explanation
ye
Very Nice !!!!!!!!!!!!!!! Thanks
sure
Thanks a lot for class bunkers like me! Anyways, university doesn't teach stuff! They want $$$. Thanks for providing good quality knowledgeable videos!
ye
Cool explanation
A,B,C,D,doit
thank you so much! just like a magic，i need to watch once again.
haha nice
just wow. thanks man
You are amazing man ❤🔥❤❤
if interview > my_math_skill : return jokes
ok
It’s “number”, not “ amount”
ok
Im kind of shocked that people consider this level of math complicated......
thanks bro.
Thanks so much!
Great job
thx
Thank u
sure
Gold
支持一下
谢谢！
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.
finally, updated again. ha
hey
Cool
hey
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! :)