Java Reference
In-Depth Information
the right, we see that the graph forms a diagonal line from lower left (with
value 0) to upper right (with value 20). Sketch this graph for yourself.
Finally, let us consider the cost for performing sequential search as the
size of the array n gets bigger. What will this graph look like? Unfortu-
nately, there's not one simple answer, as there was for finding the maximum
value. The shape of this graph depends on whether we are considering the
best case cost (that would be a horizontal line with value 1), the worst case
cost (that would be a diagonal line with value i at position i along the x
axis), or the average cost (that would be a a diagonal line with value i=2 at
position i along the x axis). This is why we must always say that function
f(n) is in O(g(n)) in the best, average, or worst case! If we leave off which
class of inputs we are discussing, we cannot know which cost measure we
are referring to for most algorithms.
3.8
Multiple Parameters
Sometimes the proper analysis for an algorithm requires multiple parameters to de-
scribe the cost. To illustrate the concept, consider an algorithm to compute the rank
ordering for counts of all pixel values in a picture. Pictures are often represented by
a two-dimensional array, and a pixel is one cell in the array. The value of a pixel is
either the code value for the color, or a value for the intensity of the picture at that
pixel. Assume that each pixel can take any integer value in the range 0 to C 1.
The problem is to find the number of pixels of each color value and then sort the
color values with respect to the number of times each value appears in the picture.
Assume that the picture is a rectangle with P pixels. A pseudocode algorithm to
solve the problem follows.
for(i=0;i<C;i++) //Initializecount
count[i]=0;
for(i=0;i<P;i++) //Lookatallofthepixels
count[value(i)]++;//Incrementapixelvaluecount
sort(count); //Sortpixelvaluecounts
In this example,
count
is an array of size C that stores the number of pixels for
each color value. Function
value(i)
returns the color value for pixel i.
The time for the first
for
loop (which initializes
count
) is based on the num-
ber of colors, C. The time for the second loop (which determines the number of
pixels with each color) is (P). The time for the final line, the call to
sort
, de-
pends on the cost of the sorting algorithm used. From the discussion of Section 3.6,
we can assume that the sorting algorithm has cost (P log P) if P items are sorted,
thus yielding (P log P) as the total algorithm cost.
