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 up being compared with other words. Note that even if we know the answer for the word "is," we end up recomputing it again.

The algorithm performs O(n²) comparison. Thus, the runtime complexity...