Sometimes the time of execution or the storage required by a program, or both, are limited. Analysis helps pinpoint parts of a program whose efficiency may be worth trying to improve, because they are executed frequently or require large amounts of storage. Such analysis can be very difficult, and simulation of the program may be needed for estimates. Simulation means that the program is executed repeatedly for appropriately chosen data, and the results are averaged or otherwise statistically analyzed. Sometimes it is possible to analyze how these requirements increase as the amount or size of the data increases, even though we cannot say what happens exactly for smaller amounts or sizes. This is called asymptotic analysis. When exact analysis cannot be done, we settle for bounds on the time and storage required.
1.8.1 Analyzing the Prime Example
1.8.2 Limits on Time and Storage