Chapter 2

The goal of section 2.1 is to define just what exactly makes an algorithm efficient and how to measure that efficiency. The section starts with a very broad and subjective definition of efficiency and goes on to explain that while the first definition makes logical sense, it's wording is too loose and thus hard to measure quantitatively. The second definition makes progress by defining an efficient algorithm as one that performs better than a brute-force search. Brute-force searches will always find an answer (if one can be found), but they are much more likely to achieve the worst case run-time and, in addition, is an “intellectual cop-out”. The third and final definition focuses on defining efficiency based on the mathematical principal of polynomial time.

Polynomial time is a way to express how an algorithm scales as the input size increases. An algorithm meets the definition of polynomial time if it scales by some constant factor c when the input size increases. So, for example, when some algorithm (defined polynomially as cN^d) has its input increased by a factor of 2–N becomes 2N–the runtime turns out to be c * 2^d * N^d, which is only a slowdown of 2^d.

While the book admits there are potentially better ways to define the efficiency of algorithms, years of trial and error have found that defining efficiency in terms of polynomial time is pretty good. Using this definition, it becomes possible to find that some particular algorithm cannot perform in polynomial time and is thereby inefficient.