16

Time-Space Trade-Off

Objectives

After reading this chapter, you should understand:

  • Time-Space Tradeoff : Meaning, Relevance and Techniques
  • How to design a Space Efficient and a Time Efficient Solution
  • The Knuth-Morris-Pratt String Matching Algorithm along with its Complexity Analysis
  • Real World Problems where Time-Space Tradeoff can be profitably employed
  • The Role of Time-Space Tradeoff in Algorithm Research

Data expands to fill the space available for storage.

—Parkinson’s Law of Data

640 K ought to be enough for anybody.

—Bill Gates, 1981

Chapter Outline

Get Design and analysis of Algorithms, 2nd Edition now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.