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.