Assignment 3: Sorting


5/5 - (2 votes)

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.
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
– 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).


There are no reviews yet.

Be the first to review “Assignment 3: Sorting”

Your email address will not be published. Required fields are marked *

Scroll to Top