This is an old revision of the document!
Table of Contents
Chapter 2 - Basics of Algorithm Analysis
Section 2.1 - Computational Tractability
This section begins by outlining some goals in how we will diagnose themes and design principles surrounding algorithms. However, the focus then shifts to the concept of efficiency. As 2.1 progresses, the author takes logical steps towards a working definition of efficiency. We desire it in our algorithms, and we need a careful definition of it such that we can achieve it in our problem-solving as we move forward.
As a Math major, I like that the focus shifted to the mathematics behind efficiency. It truly drew me to the subject matter. The author comes to a concrete definition of efficiency focusing on the idea of a polynomial runtime. This concept was a little confusing in class but is much clearer now after reading about how it works. I found it striking that such a qualitative idea such as algorithm efficiency could be reduced down to a simple quantitative checking process. I would rate the readability of this section at 10/10.
Section 2.2 - Asymptotic Order of Growth
The section continues from Computational Tractability, where we identified a definition of efficiency based on the worst-case runtime performance of an algorithm. Here, the author continues on by looking for a proper way to bound a function f(n) which expresses the runtime of an algorithm. The author examines the different ways to express bounds, through big-O, Omega, and Theta notation. The exact definitions behind these made more sense after reading back through them after covering them in class. In class, I was a little hazy between all of the variables, but they make more sense now. I found all of the explanations behind these to be fairly intuitive with one exception; I struggled to follow the converging limit of Theta on page 38. I have a solid grasp on what it means, but I am not fully confident with the material.
The author then walks through the properties of these asymptotic bounds on runtime where clear-cut, easily understandable, proofs. After these, the author covers the bounds of some common functions, including polynomials logarithms, and exponentials. These were fairly straightforward. I would rate the readability of this section at 7/10; some of the material was hard to follow and I found it less interesting than 2.1.
