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 the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.