Data Structures and Algorithms with Object-Oriented Design Patterns in Python

A Simplified Model of the Computer

The detailed model of the computer given in the previous section is based on a number of different timing parameters-- , , , , , , , , , , and . While it is true that a model with a large number of parameters is quite flexible and therefore likely to be a good predictor of performance, keeping track of the all of the parameters during the analysis is rather burdensome.

In this section, we present a simplified model which makes the performance analysis easier to do. The cost of using the simplified model is that it is likely to be a less accurate predictor of performance than the detailed model.

Consider the various timing parameters in the detailed model. In a real machine, each of these parameters is a multiple of the basic clock period of the machine. The clock frequency of a modern computer is typically between 500 MHz and 2 GHz. Therefore, the clock period is typically between 0.5 and 2 ns. Let the clock period of the machine be T. Then each of the timing parameters can be expressed as an integer multiple of the clock period. For example, , where , .

The simplified model eliminates all of the arbitrary timing parameters in the detailed model. This is done by making the following two simplifying assumptions:

All timing parameters are expressed in units of clock cycles. In effect, T=1.
The proportionality constant, k, for all timing parameters is assumed to be the same: k=1.

The effect of these two assumptions is that we no longer need to keep track of the various operations separately. To determine the running time of a program, we simply count the total number of cycles taken.