[lukev]

Oh, and to be pedantic:

> he observation that a O(n^2) problem can be broken down into n separate O(n) problems is ultimately due to system 1 reasoning: it is obviously true.

As the parent of a third grader just learning this stuff, I can assure you it isn't immediately obvious to everyone.

[atq2119]

It's also not really true.

Consider a problem like edit distance, which is solved using an n^2 dynamic program. What are the n separate problems there?

Sure, you're filling out a table with a nested loop, but that's a very mechanistic view. I don't believe that treating the n outer iterations as separate problems gives any real insight.