The Basic Axioms

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

The Basic Axioms

The running time performance of the common language runtime is given by a set of axioms which we shall now postulate. The first axiom addresses the running time of simple name binding operations:

Axiom The time required to fetch the identity of a named object from memory is a constant, , and the time required to bind a new name to an object and store that binding in memory is a constant, .

According to Axiom , the assignment statement

y = x

has running time

. That is, the time taken to fetch the identity of the object named x is

and the time taken to bind the name y to that object and store that binding in memory 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 ``1'' names an integer object with value one. Therefore, we can expect the cost of fetching the identity of the object named 1 is the same as that of fetching the identity of any other object.

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

Axiom The times required to perform elementary arithmetic operations, 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 can be accomplished in a fixed amount of time. In order for this to be feasible, the number of bits used to represent a value must also be fixed. In Python, a plain integer can be represented using 32 bits. As long as the operands and the result of an operation are all plain integers, we can say that the running time of the operation is fixed. Python also supports long integers which can have an arbitrarily large number of digits (subject to available memory). If long integers are used, then the basic arithmetic operations can take an arbitrarily long amount of time and Axiom does not apply.

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

y = y + 1

. This is because we need to fetch the identities of the two objects named y and 1; add them together giving a new object whose value is the sum; and, bind the name y to the result and store the new binding in memory.

Python syntax provides an alternative way to express the same computation:

y += 1

We shall assume that the alternative requires exactly the same running time as the original statement.

The third basic axiom addresses the method call/return overhead:

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

When a method 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 method can be evaluated. Conversely, on the return from a method, all of this work is undone. While the method call/return overhead may be rather large, nevertheless it entails a constant amount of work.

In addition to the method call/return overhead, additional overhead is incurred when parameters are passed to the method:

Axiom The time required to pass an argument to a method is the same as the time required to bind a new name to an object and store that binding in memory, .

The rationale for making the overhead associated with parameter passing the same as the time to create and store a binding is that the passing of an argument is conceptually the same as assignment of the actual parameter value to the formal parameter of the method.

According to Axiom , the running time of the statement

y = f(x)

would be

, where

is the running time of method f for input x. The first of the two stores is due to the passing of the parameter x to the method f; the second arises from the assignment to the variable y.