# How to use adversary arguments for selection and insertion sort?

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?

• Hint: It is much easier for an adversary to fool a known algorithm than all algorithms. – Raphael Apr 23 '12 at 6:42
• @Raphael I know its simple since the adversary knows the algorithm he knows the worst case where the algorithm behaves. So in the case of selection/insertion sort the complexity is O(n^2), the lower bound would be that itself ? I am little confused about a particular algorithm. Lower bound means the lower bound in the worst case ? – user5507 Apr 23 '12 at 9:03
• @user5507: Yes, usually adversarial arguments are made for proving a lower bound for a whole class of problems, not a specific algorithm. In this case you just need to specify the strategy for the adversary that results in the worst case input for these 2 algorithms. – Peter Apr 23 '12 at 12:57
• "Adversary" simply means "worst-case input" in this setting. – JeffE Apr 23 '12 at 21:12

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 in reverse sorted order). 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 cannot 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 in 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 leaves 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 chooses 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 of 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 the 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 in reverse sorted order. Indeed, in this case, the number of elements 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).

• tl;dr: The adversary's strategy is to present a reverse-sorted array as input, and then go hang out on a beach somewhere, have a few drinks, maybe learn to surf. – JeffE Apr 23 '12 at 21:17