Chapter 2

This chapter introduces us the basic mathematical tools needed for algorithm analysis.

This section introduces several ways of defining “efficiency”. The first way is the literal meaning of “efficiency”-it runs quickly. The second way is defined through comparison: if an algorithm can be designed to run faster than the most basic “brute-force search” way, then it is efficiency. The third way is that if an algorithm can be run in linear time, then it is efficient. Then the author explains why the third way is the most realistic way of defining efficiency. This section gives an evolutionary view of the concept of efficiency. It helps me understand and remember the actual definition of efficiency. Though there are many overlaps with the lecture. So the readable score is 6.

This section introduces the concept of asymptotic order of growth. First, it defines the big O, little O, and tight O. Then it shows several basic properties of the O notations as well as gives out detailed proofs. Last, it lists several common functions as examples to describe their asymptotic bounds. In class, we especially emphasized the concept of asymptotic order of growth. Thus the key points are not unfamiliar. However, due to time constrain, we skipped much of the detailed proof, which I think is not very hard to pursue, but good to go over anyway. So the readable score is also 6.