Algorithmic optimization (time & space)

Optimization tightens time or space while preserving output—replace nested scans, cache repeated subproblems, or switch representations. Always keep a correctness oracle (small brute force) when refactoring.

Why this shows up in the real world

Compilers optimize hot loops with vectorization. Mobile apps reduce memory to avoid kills.

Core idea (explained for students)

Steps: profile → find dominant term → apply known pattern (prefix sums, heap, DP). Re-benchmark after each change.

Try this in Python

def sum_squares_naive(n: int) -> int:
    return sum(i * i for i in range(n + 1))


print(sum_squares_naive(100))

Common mistakes

• Faster wrong answers—regression tests first.
• Premature micro-optimizations obscuring algorithmic fixes.

Key takeaways

• Aim for asymptotic wins before constant tweaks unless proven hot path.
• Keep golden files for tricky outputs.