Give an example where spending extra memory makes an algorithm dramatically faster, and explain what you are paying for.
When you build a lookup structure once and then use it many times.
Here is the classic example. If you want to know which positions hold the word "alpha" in a list, then searching the list every time is O of n for each word. If you build a dictionary that maps each word to its positions, then the work of building it is O of n, and every lookup after that is O of 1.
words = ["alpha", "beta", "gamma", "alpha", "delta", "beta"]
index = {}
for position, word in enumerate(words):
index.setdefault(word, []).append(position)
# One pass to build it, and then every lookup is instant.
print(index["alpha"]) # [0, 3]
print(index["beta"]) # [1, 5]
So what are you paying for? The memory that the dictionary takes. The dictionary holds one entry for every different word, and each entry holds the list of the positions where that word appears, so in this example it holds about as much space as the original list does.
That is the whole trade. You spend memory so that the time goes down. The saving is biggest when the same data is searched over and over, because then you pay the cost of building the index once and you get the fast answer every time after that.
The next question in this topic looks at the cheapest version of the trade, and the last one asks when it is worth doing.