I learn about these in ECE406.
Concepts
When implementing algorithms its usually best to start with a simple solution which may be brute-force which could be adequate because the code in question is not performance-critical. If it does not work performance-wise, the next step is to perform refinement.
Refinement here means improving the algorithm we have. The acronym BUD is used here:
- Bottleneck
- Unnecessary work
- Duplicated Work
Bottlenecks
These are rate-limiting parts of code. By removing bottlenecks we can get more throughput and get more benefit.
Unnecessary Work
This is any work we did that isn’t necessary. For example, if we found a data element that we need, we can stop searching.
Duplicated Work
This is anything that has been done more than once. For example, recomputing a value when we could just remember it.
Performance
The difference between interviews and real-life, is that in interviews, we assume that n is large enough that the other terms don’t matter. This is not always true in real life.
Accidentally Quadratic
This is when you combine two linear things and get quadratic behaviour.