You are given a sequence of \(n\) elements to sort. The input sequence…
2017
You are given a sequence of \(n\) elements to sort. The input sequence consists of \(\dfrac{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 \(\dfrac{n}{k}\) subsequences.
The lower bound on the number of comparisons needed to solve this variant of the sorting problem is :
- A.
\(\Omega (n)\) - B.
\(\Omega \bigg( \dfrac{n}{k} \bigg)\) - C.
\(\Omega(n \lg k)\) - D.
\(\Omega \bigg( \dfrac{n}{k} \: \lg \: \dfrac{n}{k} \bigg)\)
Attempted by 98 students.
Show answer & explanation
Correct answer: C
Answer: Ω(n log k)
Explanation:
There are n/k disjoint subsequences, each of size k, and the relative order between subsequences is already fixed (every element of an earlier subsequence is smaller than every element of a later subsequence). Therefore the overall sorting task reduces to sorting each subsequence independently.
Each subsequence of size k has k! possible internal orderings, so the total number of possible inputs consistent with the given inter-subsequence order is (k!)^(n/k).
A comparison-based algorithm must be able to distinguish among these possibilities, so it needs at least log2((k!)^(n/k)) = (n/k)·log2(k!) comparisons. Using log2(k!) = Θ(k log k), this equals Θ((n/k)·k log k) = Θ(n log k).
Thus the decision-tree/information-theoretic lower bound on the number of comparisons is Ω(n log k).
Note: Ω((n/k) log(n/k)) would be the lower bound if one needed to order the n/k groups themselves, but in this problem the groups are already ordered relative to each other, so that bound is not relevant.