Answers to Self-Check Problems - Building Java Programs: A Back to Basics Approach - page 1086

4. (a) O(log N )
(b) O( N )
(c) O( N 2 )
(d) O(1)
5. (a) O( N )
(b) O( N 2 )
(c) O( N )
(d) O( N )
(e) O(log B )
(f) O( N 3 )
(g) O( N ), where N is the number of lines or bytes in the file
(h) O(1)
6. The runtime complexity of both sequential searches is O( N ).
7. Binary search requires a sorted dataset because it uses the ordering to jump to the
next index. If the elements are out of order, the search isn't guaranteed to find the
target element.
8. A binary search of 60 elements examines at most 6 elements, because log 60
(when rounded up) equals 6.
9. (a) The algorithm will examine index 4 and will return 4 .
(b) The algorithm will examine indexes 4 and 6 and will return 6 .
(c) The algorithm will examine indexes 4, 6, and 7 and will return 7 .
(d) The algorithm will examine indexes 4, 2, 1, and 0 and will return 0 .
10. Because the input isn't sorted, the algorithm will examine indexes 4, 6, and 5 and
will return -1 .
11. The parameter array type should be changed to double . Also, a new swap method
will be needed that accepts a double[] as the first parameter. Here's the new
code:
public static void selectionSort(double[] a) {
for (int i = 0; i < a.length - 1; i++) {
// find index of smallest element
int smallest = i;
for (int j = i + 1; j < a.length; j++) {
if (a[j] < a[smallest]) {
smallest = j;
}
}
swap(a, i, smallest); // swap smallest to front
}
}