Why is Comparison Sorting Ω(n*log(n))? | Asymptotic Bounding & Time Complexity
Вставка
- Опубліковано 14 лип 2024
- Visit Our Website: interviewpen.com/?...
Join Our Discord (24/7 help): / discord
Join Our Newsletter - The Blueprint: theblueprint.dev/subscribe
Like & Subscribe: / @interviewpen
This is an example of a full video available on interviewpen.com. Check out our website to find more premium content like this!
Why are comparison sorting algorithms Ω(n*log(n))? In this in-depth video, we examine the fundamentals of comparison sorting algorithms and their lower bound of Ω(n*log(n)) time complexity. This video provides a comprehensive look at various comparison-based sorting techniques, such as Merge Sort, Quick Sort, and Heap Sort, and explains their significance in the field of computer science.
We delve into the decision-tree model, a powerful tool for understanding the minimum number of comparisons required by any comparison sorting algorithm. Through this model, we'll learn the reasoning behind the lower bound of Ω(n*log(n)) and why no algorithm can outperform this bound when it comes to sorting using comparisons.
Throughout the video, we'll also discuss various factors and principles that impact the performance of sorting algorithms, including their practical applications, limitations, and scenarios where they perform optimally. By the end of this video, you'll have a solid understanding of the Ω(n*log(n)) lower bound and its significance in the broader context of algorithm analysis and efficiency.
Table of Contents:
0:00 - The Core Problem
0:33 - Comparison Sorting Algorithms
2:04 - No Special Knowledge
2:25 - Visit interviewpen.com
2:44 - Logarithm Review
4:17 - Decision Tree
5:40 - Ambiguity Leading to Worst Case
6:49 - Binary Tree Levels
7:25 - Binary Tree Nodes
7:57 - Binary Tree Levels (continued)
9:27 - Worst Depth/Height
9:41 - Input Permutations
11:18 - Putting It All Together
11:39 - Relating Levels to Terminal Comparison States
13:11 - Stirling's Approximation
13:47 - Expanding Out Terms
14:56 - Left Side
15:36 - Final Equation
15:49 - The Answer
16:11 - Closing
16:46 - Visit interviewpen.com
Erratum:
2:45 - log(n) is defined for values greater than 0, rather than just greater than 1
10:39 - I meant to say "a final permutation that is the result of all decisions that led to it, etc"
Socials:
Twitter: / interviewpen
Twitter (The Blueprint): / theblueprintdev
LinkedIn: / interviewpen
Website: interviewpen.com/?...
Thanks for watching! Visit interviewpen.com/? for more great Data Structures & Algorithms + System Design content 🧎
awesome explained brother
Thanks!
great video, thank you so much!
Thanks!
Thank you for all the awesome material!
sure!
the thing i don't hear from anyone is that any comparison sorts can be reduced to two operations: binary search in new (initially empty) sorted array (search for appropriate index of another variable in there), and insertion at that index. First is O(logn) (for much more obvious reasons than all of this), second-O(n). And since the logic is that you need exactly n insertions and one binary search before every insertion, overall complexity will be just a multiplication of these. Which results in O(nlogn).
Good point, that's another way to think about it. Thanks for watching!
Very clear explanation, thanks.
What is the program that you use to make your presentations?
cool - an we use GoodNotes
This is awesome, thanks for the detailed explanation with the math! It gives a great view why we can never do better than Ω(nlogn) when it comes to comparison sorting.
thanks & thanks for watching!
(aside: we can't do better than Ω(n*log(n) rather than O(n*log(n), big O is an upperbound so it guides on bounding from above, we want to bound from below since we are looking for the best we can do. You can upperbound in the best, average, & worst case. You can lowerbound in the best, average, & worse case. Lower-bounding the best you can do makes the most sense in this discussion.)
Video Idea: Design a tiktok recomandation algorithm.
Good idea - added to backlog. Thanks for watching.
3:16 log(n) being undefined for n < 1 is cursed.
(It's actually n
Good callout - added to description