O'Reilly logo

Design and analysis of Algorithms, 2nd Edition by Himanshu B Dave

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

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

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required