O'Reilly logo

Learning Functional Data Structures and Algorithms by Raju Kumar Mishra, Atul Khot

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

Space/time trade-off

A trade-off is a balancing act: when we take something, we give away another thing!

Algorithm designs too, at times, trade-off some amount of memory to save on the overall time. Let's look at two problems to better appreciate this important concept.

A word frequency counter

Let's say we have a list of words. The task is to find how many times a word occurs in the list in order to compute every word's frequency.

Here is a brute force approach:

    w <- each word in the list, count <- 1  
      w1 <- all other words in the list 
        If (w == w1)  
           Increment count  
                  println(w, " = ", count) 

The following diagram shows the comparisons for the first two elements:

The preceding diagram shows how the algorithm works for the first two words. Each word ends ...

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