Analysis of Algorithms

Why?

Predict Performance
Compare Algorithms
Provide guarantees
Understand theoritical basis
Avoid performance bugs

Observations

Measuring the running time
- Manual/Stopwatch
- Empirical Analysis - run program for various input sizes and measure running time
- Data Analysis - Standard plot. Log-log plot, Regression
- Mathematical models
  - Total running time = sum of cost * frequency for all operations
- Theory of Algorithms
  - Tilde - for approximate model
  - Big theta - used for algorithm comparisions
  - Big Oh - used for upper bounds
  - Big Omega - used for lower bounds
Memory