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