2. Analysis of Algorithms

WIP: I am still migrating the notes to this site

Emperical Analysis

Execute program to perform experiments.
Assume power law and formulate a hypothesis for running time.
Model enables us to make predictions.

Mathematical Analysis

Analyze algorithm to count frequency of operations.
Use tilde notation to simplify analysis.
Model enables us to explain behavior

In most trivial cases, the operations (variable declaration, assignment, comparison) are approximated to take constant time.

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

Operation	Frequency
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)

Scientific Method

Mathematical model is independent of a particular system;applies to machines not yet built.
Empirical analysis is necessary to validate mathematical models and to make predictions.