Assignment 3
● Topic: Sorting
1. Show that the running time of the merge-sort algorithm on n-element sequence is
O(n log n), even when n is not a power of 2.
2. Consider a modification of the deterministic version of the quick-sort algorithm
where we choose the element at index ⌊n/2⌋ as our pivot. Describe the kind of
sequence that would cause this version of quick-sort to run in Ω(n ) time.
2
3. Describe and analyze an efficient method for removing all duplicates from a
collection A of n elements.
4. Given an array A of n integers in the range [0, n
2
- 1], describe a simple method for
sorting A in O(n) time.
5. Show that quicksort’s best-case running time is Ω(n log n).
