2.8.3 Orders of Growth

Processes can differ massively in the rates at which they consume the computational resources of space and time, as the previous examples illustrate. However, exactly determining just how much space or time will be used when calling a function is a very difficult task that depends upon many factors. A useful way to analyze a process is to categorize it along with a group of processes that all have similar requirements. A useful categorization is the order of growth of a process, which expresses in simple terms how the resource requirements of a process grow as a function of the input.
As an introduction to orders of growth, we will analyze the function count_factors below, which counts the number of integers that evenly divide an input n. The function attempts to divide n by every integer less than or equal to its square root. The implementation takes advantage of the fact that if divides and , then there is another factor such that

How much time is required to evaluate count_factors? The exact answer will vary on different machines, but we can make some useful general observations about the amount of computation involved. The total number of times this process executes the body of the while statement is the greatest integer less than The statements before and after this while statement are executed exactly once. So, the total number of statements executed is , where is the number of statements in the while body and vv is the number of statements outside of the while statement. Although it isn’t exact, this formula generally characterizes how much time will be required to evaluate count_factors as a function of the input n.
A more exact description is difficult to obtain. The constants ww and vv are not constant at all, because the assignment statements to factors are sometimes executed but sometimes not. An order of growth analysis allows us to gloss over such details and instead focus on the general shape of growth. In particular, the order of growth for count_factors expresses in precise terms that the amount of time required to compute count_factors(n) scales at the rate , within a margin of some constant factors.
Theta Notation. Let be a parameter that measures the size of the input to some process, and let be the amount of some resource that the process requires for an input of size nn. In our previous examples we took to be the number for which a given function is to be computed, but there are other possibilities. For instance, if our goal is to compute an approximation to the square root of a number, we might take to be the number of digits of accuracy required.
might measure the amount of memory used, the number of elementary machine steps performed, and so on. In computers that do only a fixed number of steps at a time, the time required to evaluate an expression will be proportional to the number of elementary steps performed in the process of evaluation.
We say that has order of growth , written (pronounced “theta of “), if there are positive constants and independent of nn such that

for any value of larger than some minimum . In other words, for large , the value is always sandwiched between two values that both scale with :

• A lower bound and
• An upper bound

We can apply this definition to show that the number of steps required to evaluate count_factors(n) grows as by inspecting the function body.
First, we choose and , so that the lower bound states that count_factors(n) requires at least steps for any . There are at least 4 lines executed outside of the while statement, each of which takes at least 1 step to execute. There are at least two lines executed within the while body, along with the while header itself. All of these require at least one step. The while body is evaluated at least times. Composing these lower bounds, we see that the process requires at least steps, which is always larger than .
Second, we can verify the upper bound. We assume that any single line in the body of count_factors requires at most p steps. This assumption isn’t true for every line of Python, but does hold in this case. Then, evaluating count_factors(n) can require at most , because there are 5 lines outside of the while statement and 4 within (including the header). This upper bound holds even if every if header evaluates to true. Finally, if we choose , then the steps required is always smaller than . Our argument is complete.