Search code examples
algorithmtime-complexitypseudocode

Creating an algorithm with better runtime

I have a matrix A with numbers A[1],A[2]...,A[n] and a matrix B (nxn) that i want to save all the possible sums. A simple algorithm that computes the B matrix is:

for i=1,2,...,n
    for j=i+1,i+2,...,n
        add the number from A[i] to A[j]
        save the results to B[i][j]
    endfor
endfor

I want to change this algorithm to be better(to have better runtime). I changed the first for i=1,2,...n to i=1 and i increase this in the end of the second for. I also think that i made more calculates that is needed.To compute B[1][5] i must compute A[1][2]+A[1][3]+A[1][4] but this sum is also in B[1][4]. So i can also compute this with less computation (B[1][4]+A[1][5]). Can anyone help me improving this algorithm?

Solution 
  • for i=1,2,...,n
    for j=i,i+1,i+2,...,n
        if i == j then B[i][j] = A[j]
        else B[i][j] = B[i][j - 1] + A[j]
    endfor
endfor