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.
Previous