OpenTube

The Smartest Algorithm No One Uses

PurpleMind

89,102 views

Go to https://ground.news/landingV8/purplem... for a better way to stay informed. Subscribe for 40% off unlimited access to world-wide coverage through my link.

The Median of Medians algorithm is one of my favorites of all time -- remember the mean, median and mode from math class? These three quantities have been etched into my brain since elementary school. But as a fourth grader, finding the median in particular always felt harder than finding the mean or the mode. For the mean and the mode, you just have to scan through the numbers once to get the answer. But the median is the “middle value” of the data, so it seems like the best method to find it is to simply sort all the numbers and then go to the middle of the sorted list. However there’s actually a way to find the median just as efficiently as finding the mean or the mode… or there are actually two ways that we explore in this video, with the second one especially being just utterly amazing. It involves taking the median of medians of certain values, and it works out to be efficient because of a certain “magic number!”

Support me on Patreon! Patreon: PurpleMindCreations
If you'd like to aid the success of this channel, this is the best way to do it! Every contribution is sincerely, greatly, appreciated.

If you or your institution is interested in sponsoring the topic of a future PurpleMind video, please contact me via purplemindcs@gmail.com!

References:
This video was heavily inspired by the following lecture: https://www.cs.cmu.edu/~15451-f23/lec...
Inspiration for the experiments from the end of the video comes largely from this really nice blog post by Russell Cohen: https://rcoh.me/posts/linear-time-med...
Quicksort: https://en.wikipedia.org/wiki/Quicksort
Quickselect: https://en.wikipedia.org/wiki/Quickse...
Median of Medians: https://en.wikipedia.org/wiki/Median_...

Brittle Rille - Reunited by Kevin MacLeod is licensed under a Creative Commons Attribution 4.0 license. https://creativecommons.org/licenses/...

This video was made using Manim, by 3Blue1Brown.

Discord Server: Discord: discord. Feel free to join!
Business Inquiries: purplemindcs@gmail.com

20 Comments

@PurpleMindCreations Creator 1 year ago Pinned

Go to ground.news/purplemind for a better way to stay informed. Subscribe for 40% off unlimited access to world-wide coverage through my link.

@VictorDuartedaSilva 1 year ago

Guaranteeing worst-case performance is important for safety reasons. A malicious user who knows the pivot selection strategy could intentionally submit a list that performs poorly, leading to a denial-of-service attack.

@apalrdsadventures 1 year ago

I love this because of how important deterministic algorithms are in time-critical systems, where it's often more important to choose an algorithmic design based on its mathematically bounded time rather than average or even the worst case time we can come up with a test case for

@noahwilliams8996 1 year ago

A worst case scenario for any algorithm could happen in the wild if it's specifically made to happen by an attacker.

@yanntal954 1 year ago

Also, quick select has worst case run time of O(n^2).
However, what is extremely cool is that there is a Quantum select algorithm that is essentially an application of Grovers algorithm!

It's run time is O(√(k*n)) where k is the elements order (large order is as hard as low order so k=n/2 is the hardest case). And that is actually the worst case time!

@Jplaysterraria 1 year ago

For some applications pivots cannot be selected randomly (e.g. when you don't have a reliable source of randomness) and the pivot it thus chosen to be the first, last or middle of the list, for those cases you can always generate a list that is the worst case for quicksort/quickselect. A well known fact is that picking the first or last elemnt is a horrible choice since it guarantees `O(n²)` runtime for sorted or almost sorted lists.

@happmacdonald 2 weeks ago

My choice of times when worst case performance becomes paramount (that is, aside from safety or defense-against-attackers) are when individual runs of the algorithm must succeed and also must carry all needed resources before they begin. For example, when performing many select operations across different lists in parallel where the next step cannot even begin until every every current list has been selected from, or when performing branchless SIMD strategies which offer the same limitation: It's like a classroom where every student is forced to wait until the slowest student completes.

@encody 2 weeks ago

Sorting a list of exactly 5 items is an immensely optimisable task, however, and you can even implement it branchlessly to take full advantage of CPU-level optimizations.

@PhilNEvo 1 year ago

That's a cool video! I think a fun little addition would have been to show a little table or graph near the end of how the geometric series converges or growth is based on how many groups you split it into. You showed 3 and 5, as a viewer you can easily accept that 5 is better, but not why 5 is optimal, without for example seeing 7 or 4 and 6~

@kuhluhOG 3 weeks ago

37:24 Well, there is software where you require scaling guarantees, not just "in 99.999% of cases it doesn't matter".

@avibi 1 year ago

I happen to have read a couple papers on median searching algorithms recently, as I was trying to find a way to reward consistency in video game scoring, and the median of the player's scores history was the first thing that came to mind (please, do tell me if you know of other direct concepts which would be representative of such an approach to game design). Admittedly, I didn't completely understand the crux of the maths behind those algorithms back then, but your video was really illustrative in that sense. They didn't mention this last fancy method either, which was truly great, focusing instead on the binmedian (idk, maybe you'd be interested in that one as well). Anyway, this was a really nice video which incidentally tackled an issue in the back of my mind. Keep it up!

@JustARandomUsername2137 9 days ago (edited)

It's often said that sorting takes O(n log n) time, but in practice if you use a 64 bit system then the array can be max 2⁶⁴ elements long, and 2⁶⁴ log 2⁶⁴ is a constant, so sorting is O(1).

And if you don't use a 64 bit system, and instead some abstract computer with infinite memory, then element access in no longer O(1), and becomes O(log n) or even O(n) if you consider speed of light.

So the big O times never really tell you exactly how long the algorithm takes, only give you a general idea with unrealistic assumptions (which is still useful).

@GruPnijla 2 weeks ago

To find instances where a fixed upper bound for runtime is prefered you would need to look into real-time computing. There you HAVE to have an upper bound for the runtime, and the worst case determines the suitability of an algorithm.

@diggigamefr2156 2 weeks ago

I m curious to see how effective the determinitic algo would be if 5 is changed to otger numbers so we can visualise why 5 is most optimal and what would happen with functions instead of number, like a sub list of lenght sqrt/(n) for example

@rodrigoqteixeira 2 weeks ago

8:00 notice that standard quicksort does in fact never take less than O(n log n), so it can't take "less than expected". I mean it can but not enough to go under n log n

@apeman5291 3 weeks ago

18:48 Ron Rivest is also the R in RSA encryption. Quite the CV!

@MatthiasGörgens 3 weeks ago

There's also a nice median finding algorithm based on soft heaps.

Though in practice I'd just use randomised quick select.

@qdiag 1 year ago

Amazing video, it definitely deserves much more views and likes!

@HankOflameo 3 weeks ago

I didn't know about quick select, even though I did take computer science classes.

@YellowBunny 1 year ago

Now that we can find the median in O(n), just use that as a pivot in quick sort for a worst case complexity of O(n·log(n)). We could call it "not quite as quick on average but quicker in the worst case sort".