How do you solve this algorithm problem?
Suppose that you are given a sequence of n elements to sort. The input sequence
consists of n/k subsequences, each containing k elements. The elements in a given
subsequence are all smaller than the elements in the succeeding subsequence and
larger than the elements in the preceding subsequence. Thus, all that is needed to
sort the whole sequence of length n is to sort the k elements in each of the n/k
subsequences. Show an �Ω(n lg k) lower bound on the number of comparisons
needed to solve this variant of the sorting problem. (Hint: It is not rigorous to
simply combine the lower bounds for the individual subsequences.)
Solve this using adversary argument.
To solve this algorithm problem and show a lower bound on the number of comparisons needed, we can use an adversary argument.
First, let's consider the number of comparisons needed to sort a single subsequence of size k. In the worst case, each element in the subsequence needs to be compared to every other element to determine its relative order. Since there are k elements, the number of comparisons needed for a single subsequence is �O(k lg k).
Now, let's assume that there exists an algorithm that can sort all n/k subsequences using fewer than �Ω(n lg k) comparisons in total. We will create an adversary strategy to prove that this is not possible.
The adversary strategy is as follows:
1. Divide the n elements into n/k subsequences, each containing k elements.
2. Randomly assign relative orderings to the elements within each subsequence. This can be done by shuffling the elements randomly.
3. Assign the first subsequence as the smallest of all subsequences and the last subsequence as the largest of all subsequences.
4. Assign the intermediate subsequences in increasing order, such that each subsequence is larger than the preceding subsequence and smaller than the succeeding subsequence.
Now, when the algorithm begins sorting the subsequences, it needs to determine the order of elements within each subsequence. Since the elements are assigned randomly, the algorithm has no prior knowledge about their actual order.
For each comparison made by the algorithm, there are two possible outcomes:
- If the outcome is consistent with the adversary's assigned order, the adversary keeps assigning random orderings to the remaining unsorted elements in the subsequences.
- If the outcome is inconsistent with the adversary's assigned order, the adversary reveals that the outcome is incorrect, and the algorithm fails to sort the subsequences correctly.
The important observation is that, since the algorithm has no knowledge about the actual order assigned by the adversary, every comparison it makes has a 50% chance of being consistent with the adversary's assigned order. Therefore, for each comparison, there is a 50% chance of the algorithm failing to sort the subsequences correctly.
Now, let's consider the number of comparisons needed by the algorithm to sort all n/k subsequences. Since every comparison has a 50% chance of being inconsistent with the adversary's assigned order, the probability of making at least one incorrect comparison is 1 - 0.5^c, where c is the number of comparisons made by the algorithm.
To ensure that the algorithm successfully sorts all subsequences, the probability of making at least one incorrect comparison should be 0. Therefore, we have:
1 - 0.5^c = 0
0.5^c = 1
c = log2(1)
c = 0
This means that the algorithm cannot make any comparisons, which is not possible. Therefore, our assumption that an algorithm exists that can sort all n/k subsequences using fewer than �Ω(n lg k) comparisons is false.
Hence, we have shown an �Ω(n lg k) lower bound on the number of comparisons needed to solve this variant of the sorting problem using an adversary argument.