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.

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*^{2}** )** for the adjacency matrix representation and

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].

Study Material, Lecturing Notes, Assignment, Reference, Wiki description explanation, brief detail

Introduction to the Design and Analysis of Algorithms : Space and Time Trade-Offs : Space and Time Trade-Offs |

**Related Topics **

Privacy Policy, Terms and Conditions, DMCA Policy and Compliant

Copyright Â© 2018-2024 BrainKart.com; All Rights Reserved. Developed by Therithal info, Chennai.