CODEWITHSUNDEEP
c++arraysperformancemathsum
Vadim
Vadim

Reputation: 1241

Fast per-column summation. Possible?

Please look at this picture:

enter image description here

Is it possible to find per-column sum for all columns faster than in O(n^2)?

Firstly I thought it's possible to make it n * log(n), if we regroup summation like this (to sum 2 rows at time, then remaining 2 rows, and then remaining 2 rows...):

enter image description here

But then I counted the number of pluses and it came out to be equal in both cases - 7 = 7 from both pictures.

So is it possible to compose such a sum in n * log(n) time, or I have fooled myself (I know there are FHT or FFT like transforms, so that might be the case)?

Upvotes: 1

Views: 476

Answers (3)

orlp
orlp

Reputation: 117761

No, our input size is O(n^2), so our algorithm can not be faster than that (because we are using all the input values).

This is assuming that n is the amount of rows, that the matrix is square (giving n^2) and there is no special relation between the elements.

Upvotes: 2

amit
amit

Reputation: 178491

It cannot be done better then O(n^2) unless you have more knowledge on the matrix.

You need to read each element in the matrix to get the correct sum for each column, so you get a lower bound of Omega(n^2)

Also, note that your idea is O(n^2), because even at the first iteration, you summaize have n * (n/2) sum ops, which is O(n^2)

Upvotes: 2

Oliver Charlesworth
Oliver Charlesworth

Reputation: 272647

No. You need to read (at least) n^2 items from memory, which takes (at least) O(n^2) time.1

1. Assuming n is the number of columns (or number of rows).

Upvotes: 2

Related Questions