I have a vector A of size n. I have to calculate the partial sum of each element and write in matrix B [i, j].
The 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?
As it is written, its algorithm is O (N 3 ). It has an implicit third loop in the part that you add A[i] s.
In the current form of the problem, there is no way to have an algorithm better than O (N 2 ). You have N*(N-1)/2 elements to fill in the array B so only the part of writing the output will already be O.
If you change the definition of B to be a one-dimensional vector where B[i] means the sum of A[1] to A[n] , then you can do in O (N). The trick is to reuse the already calculated B values in your accounts. (try doing 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).