Chapter 7 – Complexity

Once you have programmed a solution to a problem, an important question is “How long is my program going to run?” Clearly the answer to this question depends on many factors, such as the computer memory, the computer speed, and the size of the problem. For example, if your function sums every element of a very large array, the time to complete the task will depend on whether your computer can hold the entire array in its memory at once, how fast your computer can do additions, and the size of the array. The effort required to run a program to completion is the notion of “complexity,” and it is the topic of this chapter. By the end of this chapter, you should be able to estimate the complexity of simple programs and identify poor complexity properties when you see them.