News for hackers. Stuff that matters.
Re:Non-linear Thinking with CUDA by ColinWright on Saturday December 26, 2015 @07:21AM (#10793971)
Naively:

   There are n starting points
   There are n ending points
   The interval is n/2 in length on average
   Thus it requires n * n * (n/2) additions
You said:

    Generating one partial sum costs n, and
    you need to do it n times, ...
I think you need to do it n^2 times.
Re:Non-linear Thinking with CUDA by rielfowler on Saturday December 26, 2015 @07:42AM (#10794003)
There are n^2 results, right?
Re:Non-linear Thinking with CUDA by ColinWright on Saturday December 26, 2015 @12:27PM (#10794597)
Yes, and naively each of those results takes O(n) to compute.
Re:Non-linear Thinking with CUDA by rielfowler on Saturday December 26, 2015 @01:25PM (#10794752)
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.
Re:Non-linear Thinking with CUDA by ColinWright on Saturday December 26, 2015 @02:21PM (#10794921)
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?