Once Upon an Algorithm Page 5
By introducing a parameter and using it to replace concrete values we can generalize an algorithm to work in many situations. For example, if a particular getting-up algorithm contains the instruction “Wake up at 6:30 a.m.,” we can replace the concrete time value by a parameter wake-up-time, which leads to the generalized instruction “Wake up at wake-up-time.” Similarly, the cereal experience can be expanded by making the parameter fruit part of the preparation algorithm.
The flip side is that in order to execute the getting-up algorithm we now need to supply it with an input value so that the instructions can be made concrete by replacing the parameter with a time value. This is generally not a problem, but it requires a decision and is a potential source of mistakes. It all depends how valuable the variability is. An alarm clock that can wake you up at only one preset time that can never be changed is probably unacceptable, but many people can do without a parameter for selecting different alarm sounds.
Finally, an algorithm that has no parameters and thus cannot take different input values will always produce the same computation. As mentioned before, this is not a problem for algorithms that have a transient physical effect, as in the case of cake recipes, where the produced cakes get eaten, or for fetching milk, when the milk is drunk. The recomputation of the same effect makes sense in these cases. However, algorithms for computing values that can be stored and reused at later times need one or more parameters to be reusable.
Parameters are a crucial component of algorithms, but the question of how general or specific an algorithm should be does not have a simple answer. It is discussed in chapter 15.
Who Is Performing?
As we have seen, a computation is the result of executing an algorithm. This raises the question of who or what can execute an algorithm, and how. The examples have shown that people can certainly execute algorithms, but so can (electronic) computers. Are there other possibilities? And what are the requirements for executing an algorithm?
Figure 2.1 The execution of an algorithm generates a computation. The algorithm describes a method that works for a whole class of problems, and an execution operates on the representation of a particular example problem. The execution must be performed by a computer, for example, a person or a machine, that can understand the language in which the algorithm is given.
The word for somebody or something that can perform a computation is, of course, computer. In fact, the original meaning of the word referred to people who carried out computations.2 In the following, I use the term in a general sense that refers to any natural or artificial agent that can perform computations.
We can distinguish two principal cases of algorithm execution based on the abilities of the performing computer. On the one hand, there are universal computers, such as people or laptops or smart phones. A universal computer can in principle execute any algorithm as long as it is expressed in a language understandable by the computer. Universal computers establish an execution relationship between algorithms and computation. Whenever the computer executes an algorithm for a particular problem, it performs steps that change some representation (see figure 2.1).
On the other hand, there are computers that execute just one algorithm (or perhaps a set of predefined algorithms). For example, a pocket calculator contains hard-wired electronic circuits for executing algorithms to perform arithmetic computations, as does an alarm clock for making sounds at particular times. Another intriguing example can be found in cell biology.
Think about what happens in your cells millions of times while you are reading this sentence. Ribosomes are producing proteins to support your cells’ functions. Ribosomes are little machines that assemble proteins as described by RNA molecules. These are sequences of amino acids that tell the ribosome to produce specific proteins. You are alive thanks to the computation that results from the ribosomal computers in your cells reliably executing an algorithm to translate RNA molecules into proteins. But even though the algorithm used by a ribosome can produce a huge variety of proteins, this is the only algorithm that ribosomes can ever execute. While very useful, ribosomes are limited; they cannot get you dressed or find a way out of the forest.
In contrast to computers that consist of hard-wired algorithms, an important requirement for universal computers is that they understand the language in which their algorithms are given. If the computer is a machine, the algorithm is also called a program, and the language in which it is given is called a programming language.
If Hansel and Gretel wrote their memoirs and included a description of the algorithm that saved their lives, other children with access to that book could execute the algorithm only if they understood the language in which the book was written. This requirement does not apply to nonuniversal computers that carry out only fixed, hard-wired algorithms.
A requirement that applies to every kind of computer is the ability to access the representation that is used by the algorithm. In particular, a computer must be able to affect the required changes to the representation. If Hansel and Gretel were chained to a tree, the algorithm would be of no help to them, since they wouldn’t be able to change their position, which is what an execution of the way-finding algorithm requires.
To summarize, any computer has to be able to read and manipulate the representations that the algorithms operate on. In addition, a universal computer has to understand the language in which algorithms are expressed. From now on, I use the term computer to mean a universal computer.
The Cost of Living
A computer has some real work to do, a fact one is reminded of whenever the laptop gets hot while rendering high-end graphics in a video game or when the smart phone battery drains too quickly with too many apps running in the background. And the reason you have to set your alarm clock considerably earlier than the time of your first appointment is that the execution of the getting-up algorithm takes some time.
Having figured out an algorithm to solve a problem is one thing, but ensuring that an actual computation generated by the algorithm will produce a solution quickly enough is an entirely different matter. Related is the question of whether the computer in charge has enough resources available to perform the computation in the first place.
For example, when Hansel and Gretel follow the pebble trace back home, the entire computation takes as many steps as the number of pebbles that Hansel dropped.3 Note that step here means “step of the algorithm” and not “step as a part of walking.” In particular, one step of the algorithm generally corresponds to several steps taken by Hansel and Gretel through the forest. Thus the number of pebbles is a measure for the execution time of the algorithm, since one step of the algorithm is required for each pebble. Thinking about the number of steps an algorithm needs to perform its task is judging its runtime complexity.
Moreover, the algorithm works only if Hansel and Gretel have enough pebbles to cover the path from their home to the place in the forest where they are left by their parents. This is an example of a resource constraint. A shortfall of pebbles could be due either to a limited availability of pebbles, which would be a limit of external resources, or to the limited space offered by Hansel’s pockets, which would be a limit of the computer. To judge an algorithm’s space complexity means to ask how much space a computer needs to execute the algorithm. In the example, this amounts to asking how many pebbles are needed to find a path of a particular length and whether Hansel’s pockets are big enough to carry them all.
Therefore, while the algorithm may work in theory for any place in the forest, it is not clear ahead of time that a computation will succeed in practice because it may take too much time or require an amount of resources exceeding what is available. Before examining computation resources more closely, I explain two important assumptions about measuring computing costs that make this kind of analysis practical at all. In the following, I focus on the runtime aspect, but the discussion also applies to the question of space resources.
The Big Picture of Costs
An algorithm can be viewed as a generalization of many computations. As explained earlier, the differences in the computations are captured in the algorithm description by parameters, and any particular computation can be obtained through an execution of the algorithm with particular input values substituted for the parameters. In the same way, we would like to obtain a generalized description of the resource requirements of an algorithm—a description that does not just apply to a particular computation but captures all computations. In other words, we are looking for a generalization of cost descriptions. This generalization can be achieved by using parameters that can make the number of steps required for executing an algorithm dependent on the size of its input. Thus runtime complexity is a function that yields the number of steps in a computation for an input of a given size.
For example, the number of computation steps, and thus the time, required to execute the pebble-tracing algorithm is roughly equal to the number of dropped pebbles. Since paths to different places in the forest generally contain different numbers of pebbles, computations for these paths also require different numbers of steps. This fact is reflected in expressing runtime complexity as a function of the size of input. For the pebble-tracing algorithm it is easy to derive a precise measure for each computation, since the number of computation steps seems to be in one-to-one correspondence with the number of pebbles. For example, for a path with 87 pebbles, the computation requires 87 steps.
However, this is not always the case. Take another look at the path depicted in figure 1.3. That example was used to illustrate how the algorithm can get stuck, but we can also use it to demonstrate how the algorithm can produce computations that take fewer steps than there are pebbles. Since B and C are visible from D, we can pick B, and since both A and C are visible from B, we can next pick A, that is, the path D, B, A is a valid path, and since it bypasses C, the computation contains at least one less step than the number of pebbles in the path.
Note that in this case the number of steps in the computation is actually lower than predicted by the measure for the algorithm, which means that the cost of the computation is overestimated. Thus, runtime complexity reports the complexity a computation can have in the worst case. This helps us decide whether or not to execute the algorithm for a particular input. If the estimated runtime is acceptable, then the algorithm can be executed. If the computation actually performs faster and takes fewer steps, then all the better, but the worst-case complexity provides a guarantee that the algorithm will not take more time. In the case of getting up, your worst-case estimate for the time it takes to take a shower in the morning might be 5 minutes. Since this includes the time it takes for the water to get warm, your actual shower time might be shorter if someone has taken a shower before you.
Since runtime analysis is applied on the level of algorithms, only algorithms (not individual computations) are amenable to an analysis. This also means that it is possible to assess the runtime of a computation before it happens because the analysis is based on the algorithm’s description.
Another assumption for runtime complexity is that one step in the algorithm generally corresponds to several steps that are executed by the performer of the algorithm. This is obvious in the example. The pebbles are probably not placed one footstep apart, so it will take Hansel and Gretel several footsteps to get from one pebble to the next. However, each algorithm step must not cause an arbitrarily large number of computer steps. This number must be constant and relatively small compared to the number of steps taken by the algorithm. Otherwise the information about the runtime of the algorithm would become meaningless: the number of algorithm steps would not be an accurate measure for the actual runtime. A related aspect is that different computers have different performance characteristics. In the example, Hansel may have longer legs than Gretel and thus may need fewer footsteps to move between pebbles, but Gretel might be a faster walker than Hansel and thus take a specific number of footsteps in less time. All these factors can be ignored by focusing on the runtime of algorithms.
Cost Growth
Since information about runtime complexity for an algorithm is given as a function, it can capture the differences in runtime for different computations. This approach reflects the fact that algorithms typically require more time for bigger inputs.
The complexity of Hansel and Gretel’s algorithm can be characterized by the rule “The runtime is proportional to the number of pebbles,” which means that the ratio of the number of footsteps to pebbles is constant. In other words, if a path were doubled in length and thus had twice as many pebbles, the runtime would double as well. Note that this does not mean that the number of footsteps is identical to the number of pebbles, only that it increases and decreases in the same way as the input.
This relationship is called linear, and it presents itself as a straight line in a graph that plots the number of footsteps needed for any number of pebbles. In cases like this we say that the algorithm has linear runtime complexity. We also sometimes say, for short, the algorithm is linear.
Linear algorithms are very good, and in many cases the best one can hope for. To see an example of a different runtime complexity, consider the algorithm that Hansel executes when dropping the pebbles. In the original version of the story he has all the pebbles in his pocket and thus can drop them as they go into the forest. This is clearly a linear algorithm (with respect to the number of pebbles), since Hansel only takes a constant number of footsteps to reach the location for dropping the next pebble.
But now suppose that Hansel has no way of storing and concealing the pebbles. In that case, he has to go back home and fetch a new pebble for each pebble he wants to drop, which takes roughly twice the number of steps needed to get to that pebble. The total number of steps is then the sum of the steps required for each pebble. Since the distance from home increases with each dropped pebble, the total number of steps is proportional to the sum 1 + 2 + 3 + 4 + 5 + ⋯, which is proportional to the square of the number of pebbles placed.
This relationship can be illustrated by considering the distance that Hansel must travel, measured in number of pebbles. For dropping two pebbles, Hansel has to get to the place where he can drop the first pebble, go back to fetch another pebble, and then go via the first pebble to the location where he can drop the second pebble. This causes him to travel a total distance of four pebbles. For dropping three pebbles, Hansel first needs to traverse the distance required for dropping two pebbles, which we already know to be four. Then he has to go back to fetch the third pebble, which means traveling a distance of two pebbles. To place the third pebble, he then needs to go the distance of another three pebbles, which yields a total distance corresponding to 4 + 2 + 3 = 9 pebbles.
Let us consider one more case. For the fourth pebble, Hansel has traveled the distance to drop three pebbles, goes back (three pebbles), and then needs to go the distance of another four pebbles to get to the place for the fourth pebble, for a total distance of 9 + 3 + 4 = 16 pebbles. In a similar fashion, we can compute the distance required for placing five pebbles (16 + 4 + 5 = 25), six pebbles (25 + 5 + 6 = 36), and so on.
We can clearly see a certain pattern emerging, namely, that the number of steps needed by Hansel is proportional to the square of the number of pebbles placed. Algorithms that have this complexity pattern are said to have quadratic runtime, or for short, to be quadratic. The runtime of a quadratic algorithm grows much faster than that of a linear algorithm. For example, while for ten pebbles a linear algorithm takes ten steps, a quadratic algorithm needs 100. For 100 pebbles, the linear algorithm needs 100 steps, while the quadratic algorithm already needs 10,000.
Note that the actual number of steps may be higher. As mentioned, a linear algorithm may take any constant number of steps per pebble, say 2 or 3 or even 14. It may therefore take 20 or 30 or 140 steps, respectively, for a path of, say 10 pebbles. The same is true for a quadratic algorithm, whose number of steps may also need to be multiplied by a factor.
This indicates that a linear algorithm is not necessarily faster than a quadratic algorithm in all cases. With a large constant factor it may take more steps than a quadratic algorithm with a small constant factor, at least for small enough inputs. For example, a linear algorithm that takes 14 steps per pebble takes 140 steps for an input of 10 pebbles, which is more than the 100 steps a quadratic algorithm with 1 step per pebble will take. However, we can also see that with larger and larger inputs, the impact of a constant factor fades and the growth of the quadratic algorithm takes over. For example, for 100 pebbles this linear algorithm takes 1,400 steps, whereas the quadratic one already takes 10,000.
In the story, the quadratic algorithm is prohibitive and wouldn’t work. Think about the time it would take to place the last pebble. Hansel would have to walk all the way home and then back into the forest again, thus basically covering the distance into the forest three times. The parents were already impatient when he was placing pebbles using the linear algorithm.
His father said: “Hansel, what are you looking at there and staying behind for? Pay attention, and do not forget how to use your legs.”