Model answer
Memoisation stores previous results to avoid repeated recursion, and a hash index uses extra buckets to replace repeated scans with expected O(1) lookup. Both spend memory to save time.
Use the key terms, then explain the reasoning.
Algorithm Analysis
C++17
C++17Time–Space Trade-offs
Algorithms often exchange memory for speed. Good engineering chooses a balance that fits latency, hardware, energy, and environmental constraints.
What to understand
- Memoisation and lookup tables
- In-place algorithms
- Cache locality
- Energy cost of unnecessary work
Remember this
- 1Fewer operations usually means less energy
- 2Better locality reduces memory traffic
- 3The best asymptotic choice still depends on constraints
Detailed notes
Time–space trade-offs appear whenever saved results, indexes, caches, or preprocessing reduce repeated computation. The reverse trade uses recomputation or compact encodings to lower memory use.
Energy is consumed by CPU instructions, memory transfers, storage access, and network communication. Algorithmic improvements reduce these activities at their source, while cache-friendly layouts can improve both speed and energy without changing Big-O.
How it works
- 1List latency, throughput, and memory constraints.
- 2Estimate how often the operation repeats.
- 3Compare preprocessing cost with future savings.
- 4Measure representative workloads after asymptotic screening.
Where it is used
- Memoisation and dynamic programming
- Database indexes and hash tables
- Choosing compact versus precomputed graph representations
Common mistakes
- Caching data that is rarely reused
- Ignoring cache misses and data movement
- Optimising energy claims without measuring the complete workload
Implementation perspective
This is primarily a conceptual or selection topic. Use the linked implementation topics in this section to see the invariant expressed in C++.
Exam & viva
Open a prompt when you are ready to check your answer.