One of the most important features of the Parsing Expression Grammar formalism is that it is packrat parsable. This means that it can be parsed in linear time using a technique called memoization. This technique is also known as tabling in the logic programming community. The basic idea of a Parsing Expression Grammar or PEG is that you have a DSL or a domain specific language which looks exactly like a BNF, except that it is a program and its a parser. Now, these PEGs can be ambiguous and are capable of backtracking. Packrat parsers make the backtracking efficient with caching. How this works, is that the parser remembers the results of all the sub-parsers it has already run, and if it encounters the same sub-parser again, it just returns the result from the previous run. This behaviour makes packrat parsing is a very powerful technique.

When you design a language you typically want to formalize the syntax with a context-free grammar and then you feed it through a compiler and it'll generate a table-driven, bottom-up parser. Then you may have to hack on the grammar until you get it right because in order for the parsers to be efficient they need to be able to look ahead just one symbol so that they know what choice to make as they typically don't support backtracking. Of course there are versions which support infinite backtracking, but that can make your parser very inefficient. So, usually what you try to do in order to get a very efficient parser is you try and turn it into a nice grammar and then you use the generated parser to do what you like.

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:

Alright, folks! I know I keep this weblog very personal and there's art flowing all around this website, but let's talk some mathematics today! Specifically, we are here to discuss the notion of lower bounds for sorting algorithms. Now, when I say sorting algorithms, I am talking about comparison-based sorting algorithms. There are other sorting algorithms like counting sort, radix sort, bucket sort, etc. but they are a topic for another day. Now, buckle up for a long text-based post and a vomit load of mathematics, because, by the end of this article, we are going to show that any deterministic comparison-based sorting algorithm must take $\Omega(n \log n)$ time to sort an array of n elements in the worst case.

You started reading this article, and reached this point and wondered, "Wait, we are discussing the notion of lower bounds"? "What is a lower bound"? ... "To think that, what the fuck even is a bound"? Well, if you are pondering over that question, well ponder no more! I promised you a shit-ton of information and a butt-load of theory, so here we go!