The basics of algorithm analysis are a good place to begin the study of algorithms. As with any new field of study, you need to learn the terminology (“algorithm,” “problem,” “instance,” “program,” etc.). Then there are the questions of how we analyze the performance and efficiency of different algorithms and why we want to in the first place. A critical tool here is the concept of asymptotic analysis and big-oh notation. Empirical (experimental) analysis is also important, especially when formal or mathematical analysis is too difficult.
Reading¶
- Shaffer: Algorithm Analysis
- OpenDSA: Chapter 8
- DS&AA: Chapter 3
- Terminology, growth rates, asymptotic analysis, space complexity, empirical analysis
- Aho & Ullman: 3.1-3.5 [PDF]
Supplemental¶
Levitin¶
- Levitin 1.0-1.3
- Intro, fundamentals, important problem types
- Levitin 2.0-2.6
- Algorithm analysis, asymptotic notation, empirical analysis of algorithms, analyzing non-recursive (often iterative) algorithms, analyzing recursive algorithms, example: calculating Fibonacci numbers
Related¶
- Sort Benchmark — An example of runtime benchmarking for a massive version of a common problem. In 2016: 100 trillion bytes sorted in about 2 minutes! (It was 6 minutes the year before, 1 hour a year before that, 2 hours before that, 3 hours before that… Progress!)