O'Reilly logo

Design and Analysis of Algorithms by Himanshu B. Dave, Parag H. 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

Chapter 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

Chapter Outline

16.1 Introduction

16.1.1 An Example of Time-Space Trade-Off

16.2 A Quick Review of Complexity

16.3 Time-Space Trade-Off

16.3.1 Some Simple Examples

16.4 Time Space Trade Off in Algorithm Research

16.5 Case Study—Perrin Numbers

16.5.1 Perrin Numbers

16.5.2 First Try—Straight-Forward Implementation

16.5.3 Second ...

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