Appendix: Orders of Growth

from pytutor import env_diagram

Section 2.9 compared the efficiency of functions by measuring how long they took for many different inputs and graphing the results. The resulting graphs had a few characteristic shapes: a straight line for exp, a curve that flattens out for exp_fast, and a curve that bends upward for overlap. This appendix introduces the terminology that computer scientists use to describe these shapes precisely using upper and lower bounds.

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 positive 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 $k$ divides $n$ and $k < \sqrt{n}$, then there is another factor $j = n / k$ such that $j > \sqrt{n}$.

env_diagram(r'''
from math import sqrt
def count_factors(n):
    sqrt_n = sqrt(n)
    k, factors = 1, 0
    while k < sqrt_n:
        if n % k == 0:
            factors += 2
        k += 1
    if k * k == n:
        factors += 1
    return factors

result = count_factors(576)
''', cumulative=True)

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 $\sqrt{n}$. The statements before and after this while statement are executed exactly once. So, the total number of statements executed is $w \times \sqrt{n} + v$, where $w$ is the number of statements in the while body and $v$ 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 $w$ and $v$ 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 $\sqrt{n}$, within a margin of some constant factors.

Theta Notation. Let $n$ be a parameter that measures the size of the input to some process, and let $R(n)$ be the amount of some resource that the process requires for an input of size $n$. In our previous examples we took $n$ 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 $n$ to be the number of digits of accuracy required.

$R(n)$ 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 $R(n)$ has order of growth $\Theta(f(n))$, written $R(n) = \Theta(f(n))$ (pronounced “theta of $f(n)$”), if there are positive constants $k_1$ and $k_2$ independent of $n$ such that

for any value of $n$ larger than some minimum $m$. In other words, for large $n$, the value $R(n)$ is always sandwiched between two values that both scale with $f(n)$:

• A lower bound $k_1 \times f(n)$ and

• An upper bound $k_2 \times f(n)$

We can apply this definition to show that the number of steps required to evaluate count_factors(n) grows as $\Theta(\sqrt{n})$ by inspecting the function body.

First, we choose $k_1=1$ and $m=0$, so that the lower bound states that count_factors(n) requires at least $1 \times \sqrt{n}$ steps for any $n>0$. 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 $\sqrt{n}-1$ times. Composing these lower bounds, we see that the process requires at least $4 + 3 \times (\sqrt{n}-1)$ steps, which is always larger than $k_1 \times \sqrt{n}$.

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 $p \times (6 + 4 \times \sqrt{n})$ steps, because there are 5 lines outside of the while statement and 4 within (including the header), and the header is evaluated one more time than the body. This upper bound holds even if every if header evaluates to true. Finally, if we choose $k_2=10 \times p$, then the steps required are always smaller than $k_2 \times \sqrt{n}$ for any $n \geq 1$.

Therefore, the number of steps is always bounded below by $1 \times \sqrt{n}$ and above by $10 \times p \times \sqrt{n}$, and so the number of steps of count_factors(n) grows as $\Theta(\sqrt{n})$.

Example: Exponentiation¶

Section 2.9 introduced two functions for computing $b^n$. The first, exp, follows the recursive definition $b^n = b \times b^{n-1}$ with $b^0 = 1$.

>>> def exp(b, n):
        if n == 0:
            return 1
        else:
            return b * exp(b, n-1)

This is a linear recursive process that requires $\Theta(n)$ steps and $\Theta(n)$ space. Just as with factorial, we can readily formulate an equivalent linear iteration that requires a similar number of steps but constant space.

>>> def exp_iter(b, n):
        result = 1
        for _ in range(n):
            result = result * b
        return result

The second, exp_fast, uses successive squaring: $b^n = (b^{\frac{1}{2} n})^2$ when $n$ is even.

>>> def square(x):
        return x * x

>>> def exp_fast(b, n):
        if n == 0:
            return 1
        elif n % 2 == 0:
            return square(exp_fast(b, n//2))
        else:
            return b * exp_fast(b, n-1)

>>> exp_fast(2, 100)
1267650600228229401496703205376

The process evolved by exp_fast grows logarithmically with n in both space and number of steps. Computing $b^{2n}$ using exp_fast requires only one more multiplication than computing $b^n$, so the number of multiplications required for an exponent of n grows about as fast as the logarithm of n base 2. The process has $\Theta(\log n)$ growth. The difference between $\Theta(\log n)$ growth and $\Theta(n)$ growth becomes striking as $n$ becomes large. For example, exp_fast for n of 1000 requires only 15 multiplications instead of 1000.

Growth Categories¶

Orders of growth are designed to simplify the analysis and comparison of computational processes. Many different processes can all have equivalent orders of growth, which indicates that they scale in similar ways. It is an essential skill of a computer scientist to know and recognize common orders of growth and identify processes of the same order.

Constants. Constant terms do not affect the order of growth of a process. So, for instance, $\Theta(n)$ and $\Theta(500 \times n)$ are the same order of growth. This property follows from the definition of theta notation, which allows us to choose arbitrary constants $k_1$ and $k_2$ (such as $\frac{1}{500}$) for the upper and lower bounds. For simplicity, constants are always omitted from orders of growth.

Logarithms. The base of a logarithm does not affect the order of growth of a process. For instance, $\log_2 n$ and $\log_{10} n$ are the same order of growth. Changing the base of a logarithm is equivalent to multiplying by a constant factor.

Nesting. When an inner computational process is repeated for each step in an outer process, then the order of growth of the entire process is a product of the number of steps in the outer and inner processes.

For example, this version of the overlap function from Section 2.9 uses the in operator to compute the number of items in list a that also appear in list b.

>>> def overlap(a, b):
        count = 0
        for item in a:
            if item in b:
                count += 1
        return count

>>> overlap([1, 3, 2, 2, 5, 1], [5, 4, 2])
3

The in operator for lists requires $\Theta(n)$ time in the worst case, where $n$ is the length of the list b. It is applied $\Theta(m)$ times, where $m$ is the length of the list a. The item in b expression is the inner process, and the for item in a loop is the outer process. The total order of growth for this function is therefore $\Theta(m \times n)$ in the worst case.

Lower-order terms. As the input to a process grows, the fastest growing part of a computation dominates the total resources used. Theta notation captures this intuition. In a sum, all but the fastest growing term can be dropped without changing the order of growth.

For instance, consider the one_more function that returns how many items of a list a are one more than some other item of a. That is, in the list [3, 14, 15, 9], the item 15 is one more than 14, so one_more will return 1.

>>> def one_more(a):
        return overlap([x-1 for x in a], a)

>>> one_more([3, 14, 15, 9])
1

There are two parts to this computation: the list comprehension and the call to overlap. For a list a of length $n$, the list comprehension requires $\Theta(n)$ steps, while the call to overlap requires $\Theta(n^2)$ steps. The sum of steps is $\Theta(n + n^2)$, but this is not the simplest way of expressing the order of growth.

$\Theta(n^2 + k \times n)$ and $\Theta(n^2)$ are equivalent for any constant $k$ because the $n^2$ term will eventually dominate the total for any $k$. The fact that bounds must hold only for $n$ greater than some minimum $m$ establishes this equivalence. For simplicity, lower-order terms are always omitted from orders of growth, and so we will never see a sum within a theta expression.

Common categories. Given these equivalence properties, a small set of common categories emerges to describe most computational processes. The most common are listed below from slowest to fastest growth, along with descriptions of the growth as the input increases.

Other categories exist, such as the $\Theta(\sqrt{n})$ growth of count_factors. However, these categories are particularly common.

Exponential growth describes many different orders of growth, because changing the base $b$ does affect the order of growth. For instance, the number of steps in our tree-recursive Fibonacci computation fib grows exponentially in its input $n$. In particular, one can show that the nth Fibonacci number is the closest integer to

where $\phi$ is the golden ratio:

It turns out that the number of calls made by fib(n) is $2 \times \text{fib}(n+1)-1$, and so the tree-recursive process requires $\Theta(\phi^n)$ steps, a function that grows exponentially with $n$.