O'Reilly logo

Algorithms in a Nutshell by Gary Pollice, Stanley Selkow, George T. Heineman

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

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 ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required