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