Space and Time Trade-Offs

Chapter 7

Space and Time Trade-Offs

Things which matter most must never be at the mercy of things which matter less.

—Johann Wolfgang von Goethe¨ (1749–1832)

Space and time trade-offs in algorithm design are a well-known issue for both theoreticians and practitioners of computing. Consider, as an example, the problem of computing values of a function at many points in its domain. If it is time that is at a premium, we can precompute the function’s values and store them in a table. This is exactly what human computers had to do before the advent of electronic computers, in the process burdening libraries with thick volumes of mathematical tables. Though such tables have lost much of their appeal with the widespread use of electronic computers, the underlying idea has proven to be quite useful in the development of several important algorithms for other problems. In somewhat more general terms, the idea is to preprocess the problem’s input, in whole or in part, and store the additional information obtained to accelerate solving the problem afterward. We call this approach input enhancement and discuss the following algorithms based on it:

counting methods for sorting (Section 7.1)

Boyer-Moore algorithm for string matching and its simplified version sug-gested by Horspool (Section 7.2)

The other type of technique that exploits space-for-time trade-offs simply uses extra space to facilitate faster and/or more flexible access to the data. We call this approach prestructuring. This name highlights two facets of this variation of the space-for-time trade-off: some processing is done before a problem in question is actually solved but, unlike the input-enhancement variety, it deals with access structuring. We illustrate this approach by:

hashing (Section 7.3)

indexing with B-trees (Section 7.4)

There is one more algorithm design technique related to the space-for-time trade-off idea: dynamic programming. This strategy is based on recording solu-tions to overlapping subproblems of a given problem in a table from which a solu-tion to the problem in question is then obtained. We discuss this well-developed technique separately, in the next chapter of the book.

Two final comments about the interplay between time and space in algo-rithm design need to be made. First, the two resources—time and space—do not have to compete with each other in all design situations. In fact, they can align to bring an algorithmic solution that minimizes both the running time and the space consumed. Such a situation arises, in particular, when an algorithm uses a space-efficient data structure to represent a problem’s input, which leads, in turn, to a faster algorithm. Consider, as an example, the problem of traversing graphs. Re-call that the time efficiency of the two principal traversal algorithms—depth-first search and breadth-first search—depends on the data structure used for repre-senting graphs: it is  (n²) for the adjacency matrix representation and  (n + m) for the adjacency list representation, where n and m are the numbers of vertices and edges, respectively. If input graphs are sparse, i.e., have few edges relative to the number of vertices (say, m ∈ O(n)), the adjacency list representation may well be more efficient from both the space and the running-time points of view. The same situation arises in the manipulation of sparse matrices and sparse polynomi-als: if the percentage of zeros in such objects is sufficiently high, we can save both space and time by ignoring zeros in the objects’ representation and processing.

Second, one cannot discuss space-time trade-offs without mentioning the hugely important area of data compression. Note, however, that in data compres-sion, size reduction is the goal rather than a technique for solving another problem. We discuss just one data compression algorithm, in the next chapter. The reader interested in this topic will find a wealth of algorithms in such books as [Say05].