3 ms·
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
by lukev 2y ago
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 2y agoIt'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.