Page 1 of 1
2. Consider a list of n distinct numbers (a₁,..., an). Recall that the MERGESORT algorithm sorts this list using O(n log
Posted: Wed Jul 06, 2022 11:47 am
by answerhappygod
- 2 Consider A List Of N Distinct Numbers A An Recall That The Mergesort Algorithm Sorts This List Using O N Log 1 (77.85 KiB) Viewed 14 times
2. Consider a list of n distinct numbers (a₁,..., an). Recall that the MERGESORT algorithm sorts this list using O(n log n) comparisons. Can we do any better (i.e., can we sort a list using asymptotically fewer comparisons in the worst case)? In this problem, we will answer this
question in the negative. (a) How many orderings are there of the n numbers? (b) How many orderings are there of the n numbers where a₁ appears before a2? (c) How many orderings are there of the n numbers where a₁ appears before a2 and a3 appears before a4? (d) How many orderings are there of the n numbers where a₁ appears before a2 and a2 appears before az? (e) How many orderings are there of the n numbers where a₁ appears before a2 and a₁ appears before a3?