Analysis of Algorithms
Analysing algorithms can be seen from different perspectives, as an example a programmer might want to develop a working solution here as a client just wants to solve a problem efficiently. As a student it’s important to understand all the different points of view. The key measure we will focus on for analysing the effectiveness of an algorithm would be running time.
As soon as an Analytic Engine exists, it will necessarily guide the future course of the science. Whenever any result is sought by its aid, the question will arise—By what course of calculation can these results be arrived at by the machine in the shortest time? ” — Charles Babbage (1864)
Reasons to analyse Algorithms
Section titled “Reasons to analyse Algorithms”- Predict Performance
- Compare Algorithms
- Provide Guarantees (Theory of Algorithms)
- Understand Theoretical Basis (Theory of Algorithms)
Primary Practical Reason: Avoid Performance Bugs. (Confidence in completing the job in an allotted period of time).
Will my program be able to solve a large practical Input?
Section titled “Will my program be able to solve a large practical Input?”Use the scientific method to understand Performance.
Scientific Method
- Observe some features of the natural word ( Running time on our computer )
- Hypothesize a model that is consistent with the observations ( Allow us to predict the running time for larger sets )
- Predict a model that is consistent with the observations
- Verify the predictions by making further observations
- Validate by repeating until the hypothesis and observations agree
Principles
- Experiments must be reproducible
- Hypotheses must be falsifiable