Data Structures, Algorithms, & Applications in Java
Chapter 2, Exercise 30
Exercise 20(a) Part (d)
The best-case step count for n >= 0 is as below.
________________________________________________________________________
Statement s/e Frequency Total Steps
________________________________________________________________________
public static int max(...) 0 0 0
{ 0 0 0
if (n < 0) 1 1 1
throw ... 1 0 0
("MyMath.max:...");
int pos = 0; 1 1 1
for (int i = 1; i <= n; i++) 1 n+1 n+1
if (a[pos] < a[i]) 1 n n
pos = i; 1 0 0
return pos; 1 1 1
} 0 0 0
________________________________________________________________________
Total 2n + 4
________________________________________________________________________
The worst-case step count for n >= 0 is as below.
________________________________________________________________________
Statement s/e Frequency Total Steps
________________________________________________________________________
public static int max(...) 0 0 0
{ 0 0 0
if (n < 0) 1 1 1
throw ... 1 0 0
("MyMath.max:...");
int pos = 0; 1 1 1
for (int i = 1; i <= n; i++) 1 n+1 n+1
if (a[pos] < a[i]) 1 n n
pos = i; 1 n n
return pos; 1 1 1
} 0 0 0
________________________________________________________________________
Total 3n + 4
________________________________________________________________________
Exercise 20(k) Part (d)
To simplify the analysis, count the if-else as a single step.
Let n = a.length.
When n = 1,
the outer for loop is not entered and the best- and worst-case
step counts are 2.
Best- and worst-case counts for n > 1
are computed below.
_________________________________________________________________________________________
Statement s/e Frequency Total Steps
_________________________________________________________________________________________
public static void selectionSort(...) 0 0 0
{ 0 0 0
boolean sorted = false; 1 1 1
for (int size = a.length; ...) 1 2, n 2, n
{ 0 0 0
int pos = 0; 1 1, n - 1 1, n - 1
sorted = true; 1 1, n - 1 1, n - 1
// find largest 0 0 0
for (int i = 1; i < size; i++) 1 n, n(n + 1)/2 - 1 n, n(n + 1)/2 - 1
if (a[pos].lessThanOr...) pos = i; 1 n - 1, n(n - 1)/2 n - 1, n(n - 1)/2
else sorted = false; // out of order
MyMath.swap(a, pos, size - 1); 1 1, n - 1 1, n - 1
} 0 0 0
} 0 0 0
__________________________________________________________________________________________
Total 2n + 5, n2 + 4n - 3
__________________________________________________________________________________________