Learning Functional Data Structures and Algorithms

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 ...