Are you back or are you new here? If you're back, why'd you even come back? If you're new, you are in for hell. People who are back, you know what's coming. People who are new, you don't know what's coming. But you will. You will. Last time, we discussed "Why Comparison-based Sorting Algorithms have $\Omega(n log n)$ Lower Bound" and this is a follow-up to that. Also, if you haven't read that, go read the previous article first, then come back here and read this. Alright, ready? Let's go.
Today, we will discuss average-case lower bounds for comparison-based sorting algorithms. Now, I don't expect your little brain to remember everything you were spoon-fed last time, so I'll give you a quick recap. As expected, our focus in this article, once again, is comparison-based sorting Algorithms. In our last article, we were able to define a comparison-based sorting algorithm.
Also, we were able to prove that any comparison-based sorting algorithm must take $\Omega(n log n)$ time in the worst case. And, we also defined a theorem for this proof. Do you remember what it was? Of course, you don't. Here's the theorem: