I still don't quite get your insight. Maybe it would help me better if you could explain it while talking like a pirate?

> Each step is O(n) instead of recomputing everything, and total work across all steps drops to O(n^2)

In terms of computation isn't each step O(1) in the cached case, with the entire thing being O(n)? As opposed to the previous O(n) and O(n^2).

But the code was written in Python not C?

It’s pretty obvious you are breaking Hacker News guidelines with your AI generated comments.