How to use adversary arguments for selection and insertion sort?

Question

I was asked to find the adversary arguments necessary for finding the lower bounds for selection and insertion sort. I could not find a reference to it anywhere.

I have some doubts regarding this. I understand that adversary arguments are usually used for finding lower bounds for certain "problems" rather than "algorithms".

I understand the merging problem. But how could I write one for selection and insertion sort?

Answer 1

From your comment it seems you are confusing the meaning of lower bounds, upper bounds and asymptotic notation. For instance, take Insertion Sort. Its best-case running time is $\Theta(n)$ (this happens when the input is already sorted). Its worst-case running time is $\Theta(n^2)$ (this happens when the input is reverse sorted). So, since the running time falls between a linear function of $n$ and a quadratic function of $n$, you can say that the running time of Insertion Sort is both $\Omega(n)$ and $O(n^2)$. It's important to understand in this case that you can not say that the running time is $\Omega(n^2)$. Why? Because there exists an input that causes the algorithm to run in $O(n)$. However, you may say that the worst-case running time is $\Omega(n^2)$, again because there exists an input that causes the algorithm to run in $\Omega(n^2)$. We usually use the $O$ notation for the worst-case though, since we are interested to an upper bound on the number of operations done by the algorithm.

Now, let's think about an adversary argument for Insertion Sort (you may try to derive one for Selection Sort by applying the same ideas).

Consider the Insertion Sort algorithm playing against an opponent that we will call the adversary.The aim of the adversary is to provide an input X for the algorithm that maximizes the number of comparisons done by the algorithm. This is usually analyzed in the context of decision trees. A decision tree shows all possible sequences of comparisons that the algorithm could make. Each interior node of a decision tree represents a single comparison. The two children of a node represent the two outcomes of the comparison (yes/no or true/false). Each leaf represents a possible output. For sorting algorithms, the leafs are permutations of the keys. The algorithm starts at the root and follows a path down to a leaf. At each internal node, the answer for the comparison done tells the algorithm which node must be visited next. When the algorithm reaches a leaf, it outputs its corresponding permutation. The running time of an algorithm (seen as a decision tree) for a given input is the number of comparisons done in the path from the root to the output leaf. Now, the adversary has a simple strategy that will work against any comparison-based sorting algorithm, including Insertion Sort: whenever the algorithm makes a comparison, the adversary choose the answer that will eliminate the fewest possible permutations.

In general, owing to the fact that with $n$ elements there are $n!$ possible permutations, any decision tree for sorting must have at least $n!$ leaves, and so must have depth $\Omega(\log(n!)) = \Omega(n\log n)$ (by Stirling’s approximation). For Insertion Sort, the adversary may craft a particular input that causes the corresponding decision tree to have depth at least $\Omega(n^2)$.

The algorithm uses an array $A[1 .. n]$ to store the input elements and is based on the following invariant:

At the start of each iteration of the for loop, the subarray $A[1 .. j-1]$ consists of the elements originally in $A[1 .. j-1]$, but in sorted order.

In each iteration, the elements in $A[1 .. j-1]$ are therefore already in sorted order, and the algorithm examines $A[j]$ and inserts it in its final proper place, by comparing the value of $A[j]$ against the value of the elements in $A[1 .. j-1]$, starting from $A[j-1]$ and proceeding back to $A[j-2]$ and so on until $A[j]$ is no longer the greatest one in the comparison. The elements in $A[j+1 .. n]$ are in an unknown state (with regard to sort order) and will be processed in later iterations.

Here is the strategy of the adversary. Knowing that the algorithm works by inserting $A[j]$ in its proper place by moving the elements in $A[1 .. j-1]$, then the obvious strategy is to maximize in the $j$-th iteration the number of elements that must be moved in order to accommodate $A[j]$. This is easily accomplished by carefully choosing the input so that it is reverse sorted. Indeed, in this case the number of element that must be moved in each iteration is $j-1$. This leads to the $\Omega(n^2)$ worst-case running time (determined by the corresponding arithmetic series).