OK, now I don&#x27;t understand what you are trying to say.<p>There are n^2 results, each result takes O(n) to compute, so the naive algorithm is O(n^3).  That&#x27;s what you asked - why does the naive algorithm take O(n^3) - and that seems to answer your question.<p>Yes, clearly there is an overlap of some partial sums, and that&#x27;s why a less naive algorithm is sub-O(n^3).<p>So, what are you asking, or what additional point are you making?