this is question 13 from algorithms 4th edition chapter 2.2. can anyone help me

Question

this is question 13 from algorithms 4th edition chapter 2.2. can anyone help me solve it? it is not solved in the solution manual

Lower bound for average case. Prove that the expected number of compares used by any compare-based sorting algorithm must be at least ~N lg N (assuming that all possible orderings of the input are equally likely). Hint.The expected number of compares is at least the external path length of the compare tree (the sum of the lengths of the paths from the root to all leaves), which is minimized when it is balanced.

here is the url

http://www.chegg.com/homework-help/Algorithms-4th-edition-chapter-2.2-problem-13E-solution-9780321573513

thanks in advance :)

Explanation / Answer

Lower bound of all the comparison based sorting algorithms:

Comarison based sorting algoruthms are selection sort, mergesort, insertion sort,quick sort. heapsort.

Comparison algos are like decision trees.A decision tree is a full binary tree that represents the comparisons between elements that are performed by a particular sorting algorithm operating on an input of a given size.The execution iof any algorithm is like tracing a path from root to the leaf node.At each internal node the comparison takes us to either left subtree or right subtee of that node.So going from root to a leaf corresponds to one of the permutation of n! permutaions.Let m be the maximum number of comparisons.So the height of the decision tree is m. A decisio tree of height m is having 2^m leafs.So

n! < = 2^m
Taking log on both sides
log(n!) <= m
Since log(n!) = theta(nlog n) So

Therefore, any comparison based sorting algorithm must make at least nLogn comparisons  

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

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