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