16.1.5. Average Case Complexity

So, we can actually compute in the case of Quicksort what is called the average case complexity and show that this n log n. So, we will not actually show that it is n log n, but we will try to at least explain what it means to compute the average case analysis of Quicksort.

In this chunk, we introduce the concept of average case complexity specifically in the context of the Quicksort algorithm. Average case complexity assesses how an algorithm performs under typical conditions, rather than worst-case scenarios. The average case for Quicksort, as suggested, is related to n log n, which is a measure of the efficiency of the sorting process as it considers multiple random inputs.

Imagine a teacher grading a set of exams. While the worst case may be a student getting all questions wrong, the average case provides a more accurate picture of how students typically perform, which would be a mix of scores. This mix helps the teacher predict the overall outcomes better than focusing only on a single poor performance.

So, the first reason why the average case is difficult to compute is, because we need to have a way of describing all possible inputs. Now, even for a sorting algorithm all possible inputs is an infinite space, supposing I just take arrays of a fixed line, supposing I take arrays of length 4.

This chunk highlights the challenges associated with calculating average case complexity. To compute the average case, we need to analyze all possible inputs or configurations the algorithm may encounter. Since there are infinite possible arrays of a particular size (e.g., arrays of length 4), characterizing these inputs becomes complex. Each arrangement of elements leads to different behaviors for the algorithm, complicating a straightforward analysis.

Consider a bakery offering a variety of cakes. To find out which flavor is the most popular, the baker must consider every possible cake combination. Just like it would be overwhelming for the baker to analyze each unique type of cake, calculating average case complexity requires sorting through a potentially unmanageable number of configurations to find an accurate depiction of average performance.

So, we can actually think of inputs of size n to be these kind of re orderings of 1 to n or permutations of 1 to n. Now, among these permutations we do not have any preference, any one of them would come as our input.

Here, we discuss how to conceptualize the inputs to the Quicksort algorithm when determining average case complexity. By considering all possible permutations of a set of integers from 1 to n, and assuming each permutation has an equal chance of being an input, we can analyze the algorithm’s performance across this varied input set. In total, there are n factorial (n!) permutations since each number can occupy any position in the sequence.

Think of shuffling a deck of cards. Each shuffle represents a unique arrangement (or permutation), and while each arrangement is equally likely, some combinations might lead to a smoother play in a card game. In the same way, Quicksort processes numerous arrangements of numbers, and analyzing the average case requires looking at how it performs on these various arrangements.

So, we will not do the actual calculation, but if you see the average, you see the actual time it takes for all the n factorial inputs, added and divided by n factorial which is what is in probability known as calculating the expected running time.

This chunk focuses on the method used to estimate the average case running time of Quicksort. By calculating the expected running time, one sums the time taken for each configuration (time taken for each permutation of the input) and then divides this total by the number of permutations (n!). This gives a comprehensive measure of performance that shows how Quicksort will typically behave across random inputs, leading to the conclusion that its expected running time is O(n log n).

Consider a student completing various math problems where each problem takes a different amount of time. If the student averages the time across all problems to predict how long future assignments will take, they make a good estimate. Similarly, calculating the expected running time for Quicksort helps us anticipate how it performs across all possible inputs.

So, the solution is to not fix the strategy, each time I want to apply Quicksort to a recursive sub problem, I have some position 0 to n minus 1 which I need to pick as a pivot. But, rather than telling you that is going to be 0 or n minus 1 or the mid-way between 0 and n minus 1, I will say that I will choose any one of these values with equal probability.

This chunk explains one of the key insights into improving the average case complexity of Quicksort. The worst case occurs often when a poor pivot is chosen—typically the smallest or largest elements. To mitigate this problem, the strategy shifts to selecting a pivot randomly from the current segment of the array. This randomness prevents consistently poor performance and helps keep the average case performance at O(n log n) under most circumstances.

Imagine trying to pick a random piece of candy from a jar. If you always reach for the first piece, you may frequently get a flavor you dislike. However, if you close your eyes and pick randomly, you might discover a much more pleasant variety. Randomizing the pivot choice in Quicksort safeguards against consistently picking the least favorable option, allowing for better outcomes on average.

So, in practice Quicksort is very fast, as we said the worst case happens very rarely. For this reason, typically Quicksort is a default algorithm that you see that people use when you have a built in sort function.

In this final chunk, we address the practical aspects of Quicksort's usage. Despite its theoretically poor worst-case performance, Quicksort is generally very efficient in practical scenarios, which leads to its frequent adoption in programming languages as the default sorting method. Recognizing that the worst-case scenario is rare helps developers rely on Quicksort for routine sorting tasks.

Similar to a favorite restaurant that offers a dish that is typically very good but could sometimes be undercooked, Quicksort is relied on in practice despite its occasional weaknesses. Just like patrons are still willing to order their favorite dish, developers consistently turn to Quicksort for its speed and reliability in sorting data.

--