4. Algorithm Analysis Part 1
4.1. Algorithm Efficiency
There are often many approaches (algorithms) to solve a problem. How do we choose between them?
At the heart of computer program design are two (sometimes conflicting) goals.
To design an algorithm that is easy to understand, code, debug.
To design an algorithm that makes efficient use of the computer’s resources.
Goal (1) is the concern of Software Engineering
Goal (2) is the concern of data structures and algorithm analysis
4.2. How to Measure Efficiency?
Two approaches:
Empirical comparison (run programs)
Asymptotic Algorithm Analysis
What are the Critical resources?
What are the factors affecting running time?
For most algorithms, running time depends on “size” of the input.
Running time is expressed as \(\mathbf{T}(n)\) for some function \(\mathbf{T}\) on input size \(n\).
