Chapter 2

The authors begin by stating the importance of efficient and discrete algorithms. The authors then attempt to define the term efficiency, concluding that a concrete definition of efficiency is “platform-independent, instance-independent, and of predictive value with respect to increasing size.” The authors then discuss Worst-Case Running Times, explaining that it is best to analyze the worst-case of an algorithm because the worst-case does a reasonably effective job of truly capturing an algorithm's efficiency. (Average-case analysis is too opaque, as there is rarely a quantifiable average. Best-case is obviously too unrealistic).