Amey-Thakur Algorithmic complexity
Complexity describes growth, not speed. An algorithm with worse asymptotics often wins on real input sizes, and one with good asymptotics can be slow because of constants and memory behaviour. Knowing both is what makes the analysis useful.
Method
- Identify what grows. Complexity is relative to a named input: number of records, size of text, number of users. Analysis without naming the variable is meaningless.
- Count the dominant operation. The one inside the innermost loop or the recursive step. Everything else disappears into constants at scale.
- Watch for hidden loops. A lookup inside a loop that is itself linear makes the whole thing quadratic, and library calls hide this routinely (see n-plus-one-queries).
- Analyse space alongside time. An approach that is fast and holds everything in memory fails at a size the time analysis says is fine.
- Distinguish worst, average, and amortised. Hash lookups are constant on average and linear in the worst case, and which one matters depends on whether an adversary chooses your input.
- Check the real input size before optimising. Quadratic on twenty items is instant, and replacing it with a complex linear algorithm is a net loss (see performance-optimization).
- Measure to confirm. Constants, cache behaviour, and allocation dominate at small sizes, so analysis predicts the shape and measurement gives the answer (see profiling-cpu).
Boundaries
Complexity predicts scaling, not performance; two algorithms with the same class can differ by an order of magnitude in practice. Real workloads have distributions that average-case analysis may not match. Parallelism and memory hierarchy change the picture in ways simple counting does not capture (see cpu-architecture).