Algorithms in a Nutshell

Mix of Operations

As described earlier in the sidebar "The Effect of Encoding on Performance," a designer will have to consider multiple operations simultaneously. Not every operation can be optimized; in fact, optimizing one operation may degrade the execution of another operation. As an example, consider a data structure that contains operations op1 and op2. Assume that there are two different ways by which the data structure can be implemented, A and B. For the purposes of this discussion, it is not important to know anything about the data structure or the individual methods. We construct two scenarios:

Small data sets

On a base size of n=1,000 elements, mix together 2,000 op1 operations with 3,000 op2 operations.

Large data sets

On a base size of n=100,000 elements, mix together 200,000 op1 operations with 300,000 op2 operations.

Table 2-6 contains the expected result of executing implementations A and B on these two data sets. The first row of the table shows that the average cost of performing op1 on implementation A with n=1,000 sized data is assumed to be 0.008 milliseconds; the other values in the second and third columns should be interpreted similarly. The final column reflects the total expected time of execution; thus, for option A on n=1,000 sized data, we expect the time to be 2,000*0.008+3,000*0.001=16+3=19 milliseconds. Although implementation B initially outperforms the A implementation for small values of n, the situation changes dramatically when the scale of ...