Naively:<p><pre><code>   There are n starting points
   There are n ending points
   The interval is n&#x2F;2 in length on average
   Thus it requires n * n * (n&#x2F;2) additions
</code></pre>
You said:<p><pre><code>    Generating one partial sum costs n, and
    you need to do it n times, ...
</code></pre>
I think you need to do it n^2 times.