I do apologize, there are some issues with this section. At some point after the first edition of the book, it appears that the code was "optimized" and no longer clearly illustrates the points of best, worst and average case performance as it should.
At the bottom of page 26, it says: "For now, assume that the maximum element is at the beginning of the array." This should be
end of the array. Also it says: "Thus there are n·n examinations so this is an O(n) algorithm." Obviously this should read: "Thus there are n·n examinations so this is an O(n^2) algorithm."
The code should look like:
Code:
/* Returns the largest value in an array of non-negative integers */
int CompareToAll(int array[], int n)
{
int i, j;
bool isMax;
/* Make sure that there is at least one element in the array. */
if (n <= 0)
return -1;
for (i = 0; i < n; i++) {
isMax = true;
for (j = 0; j < n; j++) {
/* See if any value is greater. */
if (array[j] > array[i]) {
isMax = false; /* array[i] is not the largest value. */
}
}
/* If isMax is true, no larger value exists; array[i] is max. */
if (isMax)
return array[i];
}
}
The above code matches the discussion on page 27, while the code printed in the book doesn't. (The code printed in the book has best case performance of O(n) when the largest value is at the beginning
or end of the array and average and worst case performance of O(n^2), although the calculation of the average and worst cases doesn't quite match what's in the text.)
Again apologies for this confusion and thanks for your persistence in getting this cleared up.
--John
Big-O CompareToAll
