Mathematical Models

To understand what models are actually doing we need to utilise mathematical models. The concept was popularised in the late 60’s by Don Knuth.

*We can calculate the total running time of an operation with the below mathematical model. *

sum of cost x frequency of all operations

Analyse program to determine set of operations.
Cost depends on machine, compiler.
Frequency depends on algorithm, input data.

Cost of basic operations

Today we run experiments to understand the cost of operations. As an example we could run an add operation a billion times to average the time in nano seconds to run that operation, below are types of operations to consider:

int add
int multiply
int divide
float add
float multiply
float divide
sine
arctangent
var declaration
assignment statement
array element access
1d array allocation
2d array allocation
string length
substring extraction
string concat

It is important to understand the operation itself and how that could effect running time for example string concatenation is proportional to the length of the string so this could change the running time of the operation significantly

The sum of these basic operations present in our algorithm will be used as our first component in our mathematical model.

Example: 1-Sum

int count = 0;
for(int i = 0; i < N; i++){
  if(a[i] == 0){
    count++;
  }
}

Operations to consider and frequency

variable declaration = 2
assignment statement = 2
less than compare = N + 1
equal to compare = N
array access = N
increment = N to 2 N

Example: 2-Sum

int count = 0;
for (int i = 0; i < N; i++){
  for(int j = 0; j<N; j++){
    if(a[i] + a[j] == 0){
      count++;
    }
  }
}

Operations to consider and frequency

We have exponentially increased the frequency of our operations within the brute force method.

variable declaration = N + 2
assignment statement = N + 2
less than compare = $\frac{1}{2} (N+ 1) * (N + 2)$
equal to compare = $\frac{1}{2} N * (N - 1)$
array access = $N * (N - 1)$
increment = $\frac{1}{2} N * (N - 1) to N * (N - 1)$

It is convenient to have a measure of the amount of work involved in a computing process, even though it be a very crude one. We may count up the number of times that various elementary operations are applied in the whole process and then given them various weights. We might, for instance, count the number of additions, subtractions, multiplications, divisions, recording of numbers, and extractions of figures from tables. In the case of computing with matrices most of the work consists of multiplications and writing down numbers, and we shall therefore only attempt to count the number of multiplications and recordings. - Alan Turing (Rounding-Off Errors in Matrix Processes)

To paraphrase based on Turing’s suggestions we weight our operations by most expensive and count the frequency of those which are most expensive or executed most often as a proxy for running time. Essentially we hypothesize our running time utilising this method.