7.2 Orders of growth

As illustrated by the Fibonacci exploration, the same problem can be solved by procedures that require vastly different resources. The important question in understanding the resources required to evaluate a procedure application is how the required resources scale with the size of the input. For small inputs, both Fibonacci procedures work using with minimal resources. For large inputs, the first Fibonacci procedure never finishes, but the fast Fibonacci procedure finishes effectively instantly.

In this section, we introduce three functions computer scientists use to capture the important properties of how resources required grow with input size. Each function takes as input a function, and produces as output a set of functions:

  1.  
    The set of functions that grow no faster than $f$ grows.

  2.  
    The set of functions that grow as fast as $f$ grows.

  3.  
    The set of functions that grow no slower than $f$ grows.

These functions capture the asymptotic behavior of functions, that is, how they behave as the inputs get arbitrarily large. To understand how the time required to evaluate a procedure increases as the inputs to that procedure increase, we need to know the asymptotic behavior of a function that takes the size of input to the target procedure as its input and outputs the number of steps to evaluate the target procedure on that input.

Remember that accumulated knowledge, like accumulated capital, increases at compound interest: but it differs from the accumulation of capital in this; that the increase of knowledge produces a more rapid rate of progress, whilst the accu­mu­la­tion of capital leads to a lower rate of interest. Capital thus checks its own accumulation: knowledge thus accelerates its own advance. Each generation, therefore, to deserve comparison with its predecessor, is bound to add much more largely to the common stock than that which it immediately succeeds.
Charles Babbage, 1851

Figure 7.2 depicts the sets $O$, $\Theta $, $\Omega $ for some function $f$. Next, we define each function and provide some examples.Section 7.3 illustrates how to analyze the time required to evaluate applications of procedures using these notations.

Figure 7.2: Visualization of the sets $O(f)$, $\Omega (f)$, and $\Theta (f)$.