Collect or create content and exercises about complexity

[illicitonion]

We need to create the SDC Complexity module. This will involve finding good content we can link to, writing any content we need to fill in any gaps, and writing exercises to practice and test understanding of that content.

We have the following draft learning objectives (which we can change if we need):

Memory consumption

• Quantify the memory used by different arrays

Big-O (but we want to be quite hand-wavy about this, and not require rigorous mathematical proofs)

• Categorise algorithms into O(1), O(n), faster than O(n), slower than O(n) but tractable (e.g. O(n^2)), intractable (e.g. O(2^n))
• Give practical limits to the size of inputs to O(n^2) and O(2^n) algorithms

"Expensive" operations

• Explain what the significant/expensive operations for a particular algorithm are likely to be
• Quantify the number of significant operations taken by a particular algorithm

Pre-computing

• Identify a pre-computation which will improve the complexity of an algorithm

Trade-offs

• Give examples of trading off memory for CPU

Network as a bottleneck

• Explain limitations of needing to make network calls (e.g. from a backend to a database)

Caching

• Identify and explain how web browsers benefit from caching
• Demonstrate how caching can trade memory for CPU
• Identify and explain staleness risks with caching, and the difficulty of invalidation