Intermezzo 5: The Cost of Computation🔗

In the same spirit, timing the evaluation of a program application for specific inputs tells you how long it takes to compute the answers for those inputs—and nothing else.You may also wish to reread Local Definitions and the discussion of integrity checks in Project: Database. You may have two programs—prog-linear and prog-square—that compute the same answers when given the same inputs, and you may find that for all chosen inputs, prog-linear always computes the answer faster than prog-square. Making Choices presents just such a pair of programs: gcd, a structurally recursive program, and gcd-generative, an equivalent but generative-recursive program. The timing comparison suggests that the latter is much faster than the former.

Figure 176: A comparison of two running time expressions

How confident are you that you wish to use prog-linear instead of prog-square? Consider the graph in figure 176. In this graph, the x-axis records the size of the input—say, the length of a list—and the y-axis records the time it takes to compute the answer for an input of a specific size. Assume that the straight line represents the running time of prog-linear and the curved graph represents prog-square. In the shaded region, prog-linear takes more time than prog-square, but at the edge of this region the two graphs cross, and to its right the performance of prog-square is worse than that of prog-linear. If, for whatever reasons, you had evaluated the performance of prog-linear and prog-square only for input sizes in the shaded region and if your clients were to run your program mostly on inputs that fall in the nonshaded region, you would be delivering the wrong program.

This intermezzo introduces the idea of algorithmic analysis, which allows programmers to make general statements about a program’s performance and everyone else about the growth of a function. We thank Prabhakar Ragde for sharing his notes on connecting the first edition of this book with algorithmic analysis.Any serious programmer and scientist must eventually become thoroughly familiar with this notion. It is the basis for analyzing performance attributes of programs. To understand the idea properly, you will need to work through a text book.

Concrete Time, Abstract Time🔗

Alternatively, if we assume that predicates and selectors take some fixed amount of time, the time it takes how-many to determine the length of a list depends on the number of recursive steps it takes. Somewhat more precisely, evaluating (how-many some-list) takes roughly n times some fixed amount where n is the length of the list or, equivalently, the number of times the program recurs.

Generalizing from this example suggests that the running time depends on the size of the input and that the number of recursive steps is a good estimate for the length of an evaluation sequence. For this reason, computer scientists discuss the abstract running time of a program as a relationship between the size of the input and the number of recursive steps in an evaluation.“Abstract” because the measure ignores the details of how much time primitive steps take. In our first example, the size of the input is the number of items on the list. Thus, a list of one item requires one recursive step, a list of two needs two steps, and for a list of n items, it’s n steps.

Computer scientists use the phrase a program f takes “on the order of n steps” to formulate a claim about the abstract running time of f. To use the phrase correctly, it must come with an explanation of n, for example, “it counts the number of items on the given list” or “it is the number of digits in the given number.” Without such an explanation, the original phrase is actually meaningless.

Returning to the idea that contains-flatt? uses, on the average, an “order of steps” brings us to one more characteristic of abstract running time. Because it ignores the exact time it takes to evaluate primitive computation steps—checking predicates, selecting values, picking cond clauses—we can drop the division by 2. Here is why. By assumption, each basic step takes k units of time, meaning contains-flatt? takes time

If you had a newer computer, these basic computations may run twice as fast, in which case we would use as the constant for basic work. Let’s call this constant c and calculate:

Inserting an item is similar to finding one, so it is not surprising that the performance of insert and contains-flatt? are alike. The applications of insert to a list of l items triggers between 0 and l recursive steps. On the average, we assume it requires l/2, which means that insert takes “on the order of l steps” where l is the length of the given list.

The question is how long these lists are to which insert adds numbers. Generalizing from the above calculation, we can see that the first one is items long, the second one , and so on, all the way down to the empty list. Hence, we get that insert performs

See exercise 486 for why this is the case.

We can also proceed with less formalism and rigor. Because sort uses insert once per item on the list, we get an “order of n” insert steps where n is the size of the list. Since insert needs steps, we now see that a sorting process needs steps or “on the order of n2.”

Stop! If you paid close attention, you know that the above suggestion is sloppy. The inf program really just needs recursive steps for a list of n items. What is going on?

It shows that and differ by a small factor: 2, meaning “on the order of steps” describes inf in a world where all basic operations provided by *SL run at half the speed when compared to an inf program that runs at “the order of steps.” In this sense, the two expressions really mean the same thing. The question is what exactly they mean, and that is the subject of the next section.

Exercise 485. A number tree is either a number or a pair of number trees. Design sum-tree, which determines the sum of the numbers in a tree. What is its abstract running time? What is an acceptable measure of the size of such a tree? What is the worst possible shape of the tree? What’s the best possible shape?

The Definition of “On the Order Of”🔗

Exercise 245 tackles a different question, namely, whether we can formulate a program that decides whether two other programs are equal. In this intermezzo, we are not writing a program; we are using plain mathematical arguments.

Say we figure out that cL = 1000 and cS = 1. Then we can tabulate these abstract running times to make the comparison concrete:

This last insight is the key to the precise definition of the phrase “order of.” If a function f on the natural numbers produces larger numbers than some function g for all natural numbers, then f is clearly larger than g. But what if this comparison fails for just a few inputs, say for 1000 or 1000000, and holds for all others? In that case, we would still like to say f is better than g. And this brings us to the following definition.

Definition Given a function g on the natural numbers, O(g) (pronounced: “big-O of g”) is a class of functions on natural numbers. A function f is a member of O(g) if there exist numbers c and bigEnough such that

for all it is true that

Terminology If , we say f is no worse than g.

The key is to find the magic numbers c and bigEnough such that , which would validate that prog-linear’s performance is no worse than prog-square’s. For now, we just tell you what these numbers are:

Finally, most people use O together with a short-hand for stating functions. Thus they say how-many’s running time is O(n)—because they tend to think of n as an abbreviation of the (mathematical) function id(n) = n. Similarly, this use yields the claim that sort’s worst-case running time is O(n2) and inc’s is O(2n)—again because n2 is short-hand for the function sqr(n) = n2 and 2n is short for expt(n) = 2n.

Stop! What does it mean to say that a function’s performance is O(1)?

Exercise 486. In the first subsection, we stated that the function f(n) = n2 + n belongs to the class O(n2). Determine the pair of numbers c and bigEnough that verify this claim.

Exercise 487. Consider the functions f(n) = 2n and g(n) = 1000 n. Show that g belongs to O(f), which means that f is, abstractly speaking, more (or at least equally) expensive than g. If the input size is guaranteed to be between 3 and 12, which function is better?

Exercise 488. Compare and . Does f belong to O(g) or g to O(f)?

Why Do Programs Use Predicates and Selectors?🔗

The design of searchS fails to live up to the structural designIt really uses generative recursion. recipe. It instead takes inspiration from the idea that lists are containers that have a size. Hence, a program can check this size for 0, which is equivalent to checking for emptiness.

Although this idea is functionally correct, it makes the assumption that the cost of *SL-provided operations is a fixed constant. If length is more like how-many, however, searchS is going to be slower than searchL. Using our new terminology, searchL is using O(n) recursive steps while searchS needs O(n2) steps for a list of n items. In short, using arbitrary *SL operations to formulate conditions may shift performance from one class of functions to one that is much worse.

Stop! Conduct the experiment.

Assuming you have completed the experiment, you now know that length takes time proportionally to the size of the given list. The “S” in searchS stands for “squared” because its running time is O(n2). But don’t jump to the conclusion that thisSee Data Representations with Accumulators for how other languages track the size of a container. kind of reasoning holds for every programming language you will encounter. Many deal with containers differently than *SL. Understanding how this is done requires one more design concept, accumulators, the concern of the final part of this book.

🔗