Worst-Case Number of Comparisons in Sorting: Constructing an Adverse Input

[This page is auto-generated; please prefer to read the article’s PDF Form.]

[Prev] [Up]

Constructing an Adverse Input

For an input array a of n elements, algorithm A may require a varying number of comparisons depending upon the initial order of the elements. We are interested in the maximum among these number of comparisons, which can be called the number of comparisons in the “worst-case”, and denoted C_w.

Since we do not know how exactly A works, it is impossible to construct its worst-case input. What we will instead do is construct an adverse input and count the least number of comparisons C_d which A would do for that input. Since we must have C_w ≥ C_d, C_d will give us a lower-bound on C_w.

To construct an adverse input, we will take some array a with its keys uninitialized and modify the comparison function f as follows. f will keep track of the set S. To compare a_i and a_j, instead of using their keys, it will check how many permutations in S have a_i occurring before a_j (the subset P deﬁned earlier). If it ﬁnds |P|≥|Q|, it will respond with output “a_i < a_j” (true), otherwise it will respond with “a_i ≥ a_j” (false). This will result in the algorithm A always left with the larger of the two subsets P and Q, hence more number of candidate permutations to work with. As mentioned earlier, this larger subset must have cardinality at least |S|∕2.

Since this modiﬁed function f does not use the keys, throughout the execution of algorithm A the keys would remain unused; that’s why we could leave them uninitialized. Now, how can we really initialize the keys of the input array a, so that A would execute in exactly the same manner, but with the original comparison function f? In other words, how can we construct such adverse input?

For that, we will use the sorted output permutation from above execution of A. The keys of input array a can be initialized such that their sorted order would be the same as this permutation. For example, with n = 5, if the output permutation obtained above is (a₃,a₀,a₂,a₄,a₁), the keys of a should be chosen such that a₃ < a₀ < a₂ < a₄ < a₁. For integer keys with f based on their numerical order, this can be done, for example, by choosing the keys for a₃,a₀,a₂,a₄ and a₁ as 1,2,3,4 and 5 respectively.

We know that the output permutation must be consistent with the result of all the comparisons made in above execution of A. So, the adverse input constructed using its order must cause exactly the same comparison results and same execution ﬂow of A.

Having constructed an adverse input, let us now count C_d. After each comparison, A is left with the subset having cardinality at least |S|∕2. Since the cardinality of S is n! initially, after k comparisons, it must be at least (n!)∕2^k. So algorithm A will require at least C_d comparisons till the cardinality becomes 1, where:

n!--≤ 1 2Cd ⇔ Cd ≥ log2(n!)

And since C_w ≥ C_d, we have:

Cw ≥ log2(n!)

(1)

It can be proved that log2(n!) belongs to the set Θ(nlog2 n) (see [1]: chapter 3 section “Factorials”, and exercise 8.1-2). So we conclude that, any comparison-based sorting algorithm will do at least log2(n!) (Θ(nlog2 n)) comparisons for its worst-case input.

■

References

[1] T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein. Introduction to Algorithms, Third Edition. The MIT Press (2009).

[Prev] [Up]