2 ms·

There are n^2 results, right?

• ColinWright 11y ago
  Yes, and naively each of those results takes O(n) to compute.
  • rielfowler 11y ago
    Let me correct my self, there are n^2 results in total, when the algorithm ends. The naive algorithm is doing n times more work. That is redundant, because there is clearly an overlap of some partial sums.
    • ColinWright 11y ago
      OK, now I don't understand what you are trying to say. There are n^2 results, each result takes O(n) to compute, so the naive algorithm is O(n^3). That's what you asked - why does the naive algorithm take O(n^3) - and that seems to answer your question. Yes, clearly there is an overlap of some partial sums, and that's why a less naive algorithm is sub-O(n^3). So, what are you asking, or what additional point are you making?