A LISP programmer knows the value of everything, but the cost of
I told my dad that someday I’d have a computer that I could write
programs on. He said that would cost as much as a house. I said, “Well,
then I’m going to live in an apartment.”
This chapter develops tools for reasoning about the cost of evaluating a given expression. Predicting the cost of executing a procedure has practical value (for example, we can estimate how much computing power is needed to solve a particular problem or decide between two possible implementations), but also provides deep insights into the nature of procedures and problems.
The most commonly used cost metric is time. Other measures of cost include the amount of memory needed and the amount of energy consumed. Indirectly, these costs can often be translated into money: the rate of transactions a service can support, or the price of the computer needed to solve a problem.