1.6 Computational Complexity

Computational complexity is the study of the inherent computational cost (measured by number of arithmetic operations) of solving a problem. One measure of the efficiency of a numerical method is the number of arithmetic operations needed to solve a problem. (Others include the amount of memory used and the order in which it is used, but these issues are more properly subjects of computer science.)

The result of a complexity analysis is an estimate of how rapidly the solution time increases as the problem size increases. The use of the most efficient method has much greater importance in large problems than it does in small ones. For small problems, making the program easy to use may be the chief goal.

Even though computers continue to get faster, we cannot rely on ever-increasing speed to allow us to solve all the problems of interest. Efficiency of the algorithms used will always be important. When computers become fast enough to solve today's problems rapidly, then the scientists will want to modify their models to include details that were too expensive to include in the original models. Our notion of a "large" problem will change along with the speed of the machines and the efficiency of the algorithms.