TRUE or FALSE ? justification required.

1. We can sort 5 keys with 6 comparisons in the worst-case.

2. We can sort 4 keys with 5 comparisons in the worst-case.

3. We can find the median of n keys in O(n) time.

4. We can find the smallest of n lg n keys in n lg n 1 comparisons.

5. We can find the 100-th smallest and 100-th largest of n keys (n > 1000) within O(n) comparisons.

6. We can find the minimum and maximum of n keys with n + dlg ne 2 comparisons.

Problem 3. (18 POINTS) TRUE or FALSE ? No justification required. (An T or F is neither TRUE nor FALSE; they would be considered wrong.) All time bound are for the worst-case. 1. We can sort 5 keys with 6 comparisons in the worst-case. 2. We can sort 4 keys with 5 comparisons in the worst-case 3. We can find the median of n keys in O(n) time. 4. We can find the smallest of nlgn keys in nlgn - 1 comparisons 5. We can find the 100-th smallest and 100-th largest of n keys (n > 1000) within O(n) comparisons 6. We can find the minimunn and maximum of n keys with n +Ign-2 comparisons