# Cormen Edition 3 Exercise 8.1 Question 3 (Page No. 194)

68 views
Show that there is no comparison sort whose running time is linear for at least half of the $n!$ inputs of length $n$.What about a fraction of $1/n$ inputs of length $n$? What about a fraction $1/2^n$?

## Related questions

1
99 views
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 ... this variant of the sorting problem. (Hint: It is not rigorous to simply combine the lower bounds for the individual subsequences.)
Obtain asymptotically tight bounds on $lg\ (n!)$ without using Stirling’s approximation. Instead, evaluate the summation $\sum_{k=1}^{n} lg\ k$.
BUCKET-SORT(A) 1 let B[0...n-1] be a new array 2 n = A.length 3 for i – 0 to n – 1 4 make B[i] an empty list 5 for i = 1 to n 6 insert A[i] into list B[nA[i]] 7 for i = 0 to n – 1 8 sort list B[i] with insertion sort 9 concatenate the lists B[0] , B[1] , ….,B[n-1] together in order illustrate the operation of BUCKET-SORT on the array $A=\langle .79,.13,.16,.64,.39,.20,.89,.53,.71,.42\rangle$