This notebook contains an excerpt from the Python Programming and Numerical Methods - A Guide for Engineers and Scientists, the content is also available at Berkeley Python Numerical Methods.
The copyright of the book belongs to Elsevier. We also have this interactive book online for a better learning experience. The code is released under the MIT license. If you find this content useful, please consider supporting the work on Elsevier or Amazon!
< Chapter 7 Summary and Problems | Contents | 8.1 Complexity and Big-O Notation >
Chapter 8. Complexity¶
CHAPTER OUTLINE¶
Motivation¶
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.