Data Structures and Algorithms with Object-Oriented Design Patterns in C++

## The Basic Axioms

The running time performance of the C++ virtual machine is given by a set of axioms which we shall now postulate. For now we consider only operations on integers. The first axiom addresses the running time of simple variable references:

Axiom  The time required to fetch an integer operand from memory is a constant, , and the time required to store an integer result in memory is a constant, .

According to Axiom , the assignment statement

`y = x;`
has running time . I.e., the time taken to fetch the value of variable x is and the time taken to store the value in variable y is .

We shall apply Axiom  to manifest constants too: The assignment

`y = 1;`
also has running time . To see why this should be the case, consider that the constant typically needs to be stored in the memory of the computer, and we can expect the cost of fetching it to be the same as that of fetching any other operand.

The next axiom addresses the running time of simple arithmetic operations on integers:

Axiom  The times required to perform elementary operations on integers, such as addition, subtraction, multiplication, division, and comparison, are all constants. These times are denoted by , , , , and , respectively.

According to Axiom , all the simple operations on integers can be accomplished in a fixed amount of time. In order for this to be feasible, the number of bits used to represent an integer must be fixed. Typically, between 16 and 64 bits are used to represent an integer. It is precisely because the number of bits used is fixed that we can say that the running times are also fixed. If arbitrarily large integers are allowed, then the basic arithmetic operations can take an arbitrarily long amount of time.

By applying Axioms  and , we can determine that the running time of a statement like

`y = y + 1;`
is . This is because we need to fetch two operands, y and 1; add them; and, store the result back in y.

C++ syntax provides several alternative ways to express the same computation:

```y += 1;
++y;
y++;```
We shall assume that these alternatives require exactly the same running time as the original statement.

Axiom  The time required to call a function is a constant, , and the time required to return from a function is a constant, .

When a function is called, certain housekeeping operations need to be performed. Typically this includes saving the return address so that program execution can resume at the correct place after the call, saving the state of any partially completed computations so that they may be resumed after the call, and the allocation of a new execution context (stack frame  or activation record ) in which the called function can be evaluated. Conversely, on the return from a function, all of this work is undone. While the function call/return overhead may be rather large, nevertheless it entails a constant amount of work.

`y = f (x);`