This section discusses computational tractability, what efficiency is, and why we have the current methods that we do in order to measure it. The worst-case analysis of an algorithm has been found to do a reasonable job of capturing its efficiency in practice; that is, how long will the algorithm take to run in the worst possible case. This chapter defines an efficient algorithm as one that has a polynomial running time.

Efficiency is hugely important because algorithms need to be efficient in order to be practical.

Seeing the chart on page 34 really brings some perspective on just how terrible exponential and nfactorial functions are according to their runtimes. This section was very interesting 9/10.