From Introduction to Algorithms ISBN:978-0-262-03293-3 You are given a a sequenc

Question

From Introduction to Algorithms ISBN:978-0-262-03293-3 You are given a a sequence of 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 preceeding subsequences. 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 log 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.)

Explanation / Answer

Suppose that S be a sequence of n elements and has properties described in statements of this problem. Consider the decision tree of height h for any comparison sort for S. There are n/k subsequences in S, every one of them can be in any arbitrary order.

Thus there are (k!)^n/k permutations of S possible.

So any decision tree for sorting S has at least (k!)^n/k leaves.

As a binary tree of height h has at most 2^h leaves, we have 2^ h (k!)^n/k.

As a result

2^ h (k!)^n/k

h lg(k!)^n/k

h = (n/k) lg(k!)

h (n/k) lg(k/2)^k/2

h = (n/2) lg(k/2)

That means that there exist at least on path in a decision tree having length at least (n/2) lg(k/2). Hence the worst-case running time of any comparison-based sorting algorithm for S is ((n/2) lg(k/2)) = (n lg k).

Related Questions

Navigate

• Browse (All)
• Browse F
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.