Algorithm Analysis - Data Structures and Algorithm Analysis - page 78

Is this a good representation for the cost of this algorithm? What is actu-
ally being sorted? It is not the pixels, but rather the colors. What if C is much
smaller than P? Then the estimate of (P log P) is pessimistic, because much
fewer than P items are being sorted. Instead, we should use P as our analysis vari-
able for steps that look at each pixel, and C as our analysis variable for steps that
look at colors. Then we get (C) for the initialization loop, (P) for the pixel
count loop, and (C log C) for the sorting operation. This yields a total cost of
(P + C log C).
Why can we not simply use the value of C for input size and say that the cost
of the algorithm is (C log C)? Because, C is typically much less than P. For
example, a picture might have 1000 1000 pixels and a range of 256 possible
colors. So, P is one million, which is much larger than C log C. But, if P is
smaller, or C larger (even if it is still less than P), then C log C can become the
larger quantity. Thus, neither variable should be ignored.

3.9 Space Bounds

Besides time, space is the other computing resource that is commonly of concern
to programmers. Just as computers have become much faster over the years, they
have also received greater allotments of memory. Even so, the amount of available
disk space or main memory can be significant constraints for algorithm designers.
The analysis techniques used to measure space requirements are similar to those
used to measure time requirements. However, while time requirements are nor-
mally measured for an algorithm that manipulates a particular data structure, space
requirements are normally determined for the data structure itself. The concepts of
asymptotic analysis for growth rates on input size apply completely to measuring
space requirements.

Example3.16 What are the space requirements for an array of n inte-
gers? If each integer requires c bytes, then the array requires cn bytes,
which is (n).

Example3.17 Imagine that we want to keep track of friendships between
n people. We can do this with an array of size nn. Each row of the array
represents the friends of an individual, with the columns indicating who has
that individual as a friend. For example, if person j is a friend of person
i, then we place a mark in column j of row i in the array. Likewise, we
should also place a mark in column i of row j if we assume that friendship
works both ways. For n people, the total size of the array is (n 2 ).