Linear-Time Median Algorithm (Making Quicksort go Fast!)

Here we show that we can find the median of an array (or in general, the kth smallest element) in linear time, versus just sorting the array and returning the kth element. This in turn speeds up Quicksort, because the pivot can now be the median element (findable in linear time), and we now get the guaranteed performance of Mergesort, which was O(n log n). Before, Quicksort can at worst pick the "first" element every time, which caused a O(n^2) runtime to occur.

Timestamps: 0:00 - Intro 0:31 - Problem Statement 3:28 - Can we find a good pivot? 6:37 - Generalize the problem (finding kth smallest/largest) 7:45 - Kth Smallest/Largest "Simple" Recursive Algorithm 13:25 - Can we make this algorithm faster? 15:10 - Median of Medians 20:50 - Modifying Kth Smallest/Largest Algorithm 24:55 - Proving this algorithm is faster 29:00 - Determining algorithm runtime

Donation (appears on streams): https://streamlabs.com/easytheory1/tip Paypal: https://paypal.me/easytheory Patreon: https://www.patreon.com/easytheory Discord: https://discord.gg/SD4U3hs

Youtube Live Streaming (Sundays) - subscribe for when these occur.

Merch: Language Hierarchy Apparel: https://teespring.com/language-hierarchy?pid=2&cid=2122 Pumping Lemma Apparel: https://teespring.com/pumping-lemma-for-regular-lang

If you like this content, please consider subscribing to my channel: https://www.youtube.com/channel/UC3VY6RTXegnoSD_q446oBdg?sub_confirmation=1

Gold Supporters: Micah Wood Silver Supporters: Timmy Gy

▶SEND ME THEORY QUESTIONS◀ ryan.e.dougherty@icloud.com

▶ABOUT ME◀ I am a professor of Computer Science, and am passionate about CS theory. I have taught many courses at several different universities, including several sections of undergraduate and graduate theory-level classes. ... https://www.youtube.com/watch?v=n8cyxDtp9t4