In the previous mission, we learned how to analyze the time complexity of an algorithm. We saw examples of linear time algorithms.

In this second mission of our Algorithm Complexity course, we will see another kind of time complexity: constant time complexity. We will also learn the core operations that a computer can perform and how a computer structures data into its memory.

Suppose that you have a dataset on your hard drive. Let's assume it occupies the full hard drive. Imagine that you want to send it to someone living on the other side of the world. One way to do so is to send it via the Internet. Assuming constant upload and download rates, the time it takes for the file to arrive should be proportional to the capacity of your hard drive. This is, therefore, a linear time algorithm to send the hard drive contents.

Imagine now that instead of sending the file over the Internet, you take a flight and hand deliver the hard drive. Assuming constant flight times, regardless of the size of the hard drive, the time it will take you to deliver the data is constant. Therefore, this is a constant time algorithm for sending the hard drive contents.

Throughout this mission, you’ll dig much deeper into this concept of constant time complexity.

Objectives

  • Identify constant time operations.
  • Learn how computers manage memory.
  • Refine the way of computing time complexity models that take into account functions.
  • Identify hidden function calls in Python.
  • Learn the ins and outs of how lists and strings are stored in memory.

Mission Outline

1. Constant Time Complexity
2. Constant Time Complexity in Python
3. Complexity of Function Calls
4. Hidden Function Calls
5. Fundamental Operations of a Computer
6. Amortized Analysis of Append
7. List Complexities
8. Arithmetic Operations
9. String Concatenation
10. Hidden Python Optimizations
11. Next Steps
12. Takeaways