Time–Space trade off in data structures and Algorithms

Let’s learn about Time–Space trade off , what is needed for a time-space trade-off?

Definition:-

A space-time or time-memory trade-off in computer science is a way of solving a problem in:-

• Less time by using more memory
• By solving in very little space by spending a long time.

 

Example

Types  of Time-Space Trade-off

1. Lookup vs. recalculation
2. Compressed vs. uncompressed
3. Re-rendering vs. stored images
4. Smaller code vs. loop unrolling

 

• Lookup vs. recalculation

An algorithm involving a lookup table is an implementation can include the entire table, which reduces computing time, but increases the amount of memory needed, or it can compute table entries as needed, increasing computing time, but reducing memory requirements.

 

 

• Compressed vs. uncompressed

The problem of data storage can also be handled by using space and time tradeoff of algorithms. If data is stored is not compressed, it takes more space but access takes less time than if the data were stored compressed (since compressing the data reduces the amount of space it takes, but it takes time to run the decompression algorithm). It is depending upon the particular instance of the problem, either way is practical. There are also rare instances where it is possible to directly work with compressed data, such as in the case of compressed bitmap indices, where it is faster to work with compression than without compression.

 

 

• Re-rendering vs. stored images

In this case, storing only the SVG source of a vector image and rendering it as a bitmap image every time the page is requested would be trading time for space; more time used, but less space. Rendering the image when the page is changed and storing the rendered images would be trading space for time; more space used, but less time. This technique is more generally known as caching.

 

• Smaller code vs. loop unrolling

This technique is commonly used to makes the code longer for each iteration of a loop, but it saves the computation time required for jumping back to the beginning of the loop at the end of each iteration. Larger code size can be traded for higher program speed when applying loop unrolling

 

I hope guys like and comment this Time–Space trade off

Read more about Data Structures

Introduction to data structures

Analysis of algorithms