Am I computing these summations the right way?

57 Views Asked by At

Given Algorithm:

 for i = 1, 2, . . . , n  
     for j = i + 1, i + 2, . . . , n
         Add up array entries A[i] through A[j]
         Store the result in B[i, j]
    Endfor
 Endfor

My attempt: Solving for worst case using Big-O notation:

$$\sum_{i=1}^{n} \sum_{j=i+1}^{n}n = \sum_{i=1}^{n}n(n-i) = \frac{n^{3}}{2}-\frac{n^{2}}{2}$$ Therefore for the worst case running time we have: $$O(n^3)$$ Is that correct? Or did I not interpreted the algorithm correctly.