Partial sum of elements of a vector in O(n) or O(log n)

Asked

Viewed 464 times

2

I have an A vector of size n. I have to calculate the partial sum of each element and write in the matrix B[i,j].

Pseudo-code shows a solution O(n 2);

  For i = 1, 2, . . . , n
    For j = i + 1, i + 2, . . . , n
      B[i, j] <- A[i] + A[i+1] + ... +  A[j];
   Endfor
  Endfor

Is there an O(n) or O(log n) solution? What would it be like?

algorithm

1 answer

2


As written, its algorithm is O(N3). There’s a third loop implicit in the part where you add the A[i]s.

In the current form of the problem, there is no better algorithm than O(N2). You have N*(N-1)/2 elements to fill in the matrix B then only the part of writing the output will already be O(N2).

If you change the definition of B to be a one-dimensional vector where B[i] means the sum of A[1] until A[n], I can do it in O(N). The trick is to reuse the values already calculated B on your accounts. (try to do this without asking before - it’s a great exercise)

O(log N) does not give because at least you will have to go through the vector A once to read its elements and this will already give O(N).

Browser other questions tagged algorithm

You are not signed in. Login or sign up in order to post.