Homework 14

Questions 8.15 from the course text.

Solution

1. Sorting not required. Scan through the list of numbers and keep a running minimum. Return this as the minimum of the list. T(n) is in O(n).
2. Sorting not required. Scan through the list and keep a running maximum. Return this as the maximum of the list. T(n) is in O(n).
3. Sorting not required. Sum all the numbers and divide by n. T(n) is in O(n).
4. Sort the numbers first. Then pick out the middle element, or the average of the two elements on either side of the middle (if n is even). T(n) is in O(n Log n).
5. Sort the numbers first. Then scan through the sorted list and keep a running maximum count of the number of occurrences of each element. Return this as the mode. T(n) is in O(n Log n).