Welcome to the Complexity module

Until now, you have written programs which handle small amounts of data. We haven’t worried very much about the cost. We’ve been living like kings! But when we write commercial code, we need to think:

• How much time does your code take to run?
• How much memory does it use?
• How does it scale when dealing with lots of data?

These are crucial questions in software engineering. This is because we write code for many users, not just for ourselves.

This module explores computational complexity. This means the resources (like time and memory) an algorithm consumes. We’ll build mental models to:

• analyse and compare different approaches
• identify bottlenecks
• and make informed trade-offs to improve our performance.

How to succeed

• Work through each section. Read the explanations and engage with the suggested activities. You will also be reading Chapter 8 of How Computers Really Work.
• Focus on the learning objectives. Check you can meet the objectives listed for each section.
• Build toy solutions. Build your own small programs to test the ideas presented in the prep.
• Prepare for discussion. You will be teaching a concept in class.

Concepts you will teach:

You get to choose

1. Space: caching, precomputing, memoisation, memory consumption
2. Time: complexity of algorithms (eg logarithmic, exponential), expensive operations, I/O, thrifty queries

Buckle up!