Search code examples
c++algorithmpseudocode

How to calculate closed form for following pseudocode?

I need help with the following problem:

Analyze the running time of the following program fragment and write pseudocode (in C++) which will output the value of this but which runs in constant time. You may assume that n is given earlier in the program.

 sum = 0
 for i from 1 to n-1 do
   for j from i to n*n do
     sum = sum + i

What I am up to: I know that the time complexity is O(n2) for the following program fragment and that the:

sum = n*n*(n)*(n-1)/2-(n-1)*n*(2*(n-1)+1)/6+(n-1)*n/2;

I am unsure how to put this into pseudocode format. Any help will be greatly appreciated, thank you!

Solution 
  •  sum <- n*n*(n)*(n-1)/2-(n-1)*n*(2*(n-1)+1)/6+(n-1)*n/2

    That's all. There is no need in loops when you know closed-form formula.

    Calculation with such formula has constant time complexity