# Is there a faster than O(n^2) way to compute a vector of length n from another vector and an n by n matrix?

$$A$$ is an array of length $$n$$
$$B$$ is an $$n\times n$$ matrix \

I want to return an array C of size n such that:
$$C_{i} = \sum_{j=1}^{n} \max(0, a_i - b_{ij})$$

In pseudocode it could be like below

for i = 1 to n:
C[i] = 0
for j = 1 to n:
C[i] += max(0, a[i] - b[i,j])

this runs on O(n^2) but it is possible to lower that.

• Your pseudocode has a tiny mismatch with your formula: instead of a[i] it has a[1]. So it would only check the first element of array. I would edit it myself, but it's illegal to send edits under 6 characters. Commented Sep 29, 2022 at 0:55
• Thanks @user28434 I have just corrected that Commented Sep 29, 2022 at 4:16
• What made you think there could be a faster solution? Commented Sep 29, 2022 at 13:38
• Is there anything you can precompute, or are A and B both fresh and new and arbitrary on each run? Commented Sep 30, 2022 at 16:34

That's not possible. You have to read in the entire $$B$$ matrix to determine the correct answer, which fundamentally requires $$O(n^2)$$ time.

A key observation is that if $$i$$-problems are completely independent, you need to compute $$n$$ sums of the form

$$s=\sum_{j=1}^n\max(0,a-b_j).$$

With $$a=0$$ and all $$b_j<0$$, we get the even simpler form

$$-s=\sum_{j=1}^nb_j$$ which is a sum of $$n$$ terms and takes $$\Omega(n)$$ additions. (If parallelized, this can be lowered to $$\Omega(\lg(n))$$ using $$n$$ processors.) In the general case, you need the same amount of comparisons.

If you know a priori that only few terms are such that $$b_j and you can efficiently determine which ones, then you can avoid accumulating the zeroes.

More interesting question is when $$b$$ is a sparse matrix. Then, two cases: if

• $$a\le0$$, just add the terms $$\max(0, a_i-b_{ij})$$ for all $$i$$. But if
• $$a>0$$, add $$na_i$$ and the terms $$\max(-a_i,-b_{ij})$$ or $$-\min(a, b_{ij})$$.

While the worst-case complexity is $$O(n^2)$$, the following special case might be of interest for some applications of this algorithm:

If:

• $$B$$ does not contain negative values

and:

• $$a_i = 0$$

Then $$C_i = 0$$, with no need to consider the matrix entries $$b_{i1}$$ to $$b_{in}$$.

This short circuit may make the algorithm behave linear in practice if $$A$$ is rather sparse and the condition of $$B$$ containing no negative numbers holds.

• I already gave more general rules, for the dense and sparse case.
– user16034
Commented Sep 28, 2022 at 20:35