So far in our Algorithm Complexity course, we learned how to model the behavior of algorithms in terms of execution time. In the past, speed was the main bottleneck of algorithms; even though computers did not have a lot of memory, the amount of data that we had to process was relatively small.

In recent years, things have drastically changed, and now we have huge amounts of data available and ready to be fed into all sorts of algorithms. For this reason, limiting the amount of memory that an algorithm requires has become critical.

In this mission, we will learn how to model the memory requirements of an algorithm. This process is similar to what we do to model the time complexity.

Objectives

  • Learn how to evaluate the space complexity of an algorithm
  • Learn about tradeoffs between time and space

Mission Outline

1. Space Complexity
2. Primary and Secondary Memory
3. Memory and Speed Tradeoff
4. Pair Sums Problem
5. Precomputing to Reduce Time Complexity
6. Balancing Time and Space
7. Precomputing to Reduce Time Complexity
8. Challenge
9. Next Steps
10. Takeaways