5
$\begingroup$

$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.

$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$
    – user28434
    Sep 29 at 0:55
  • 1
    $\begingroup$ Thanks @user28434 I have just corrected that $\endgroup$
    – Macosso
    Sep 29 at 4:16
  • 1
    $\begingroup$ What made you think there could be a faster solution? $\endgroup$
    – U. Windl
    Sep 29 at 13:38
  • $\begingroup$ Is there anything you can precompute, or are A and B both fresh and new and arbitrary on each run? $\endgroup$
    – Pablo H
    Sep 30 at 16:34

3 Answers 3

30
$\begingroup$

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.

$\endgroup$
10
$\begingroup$

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<a$ 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})$.
$\endgroup$
1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ I already gave more general rules, for the dense and sparse case. $\endgroup$ Sep 28 at 20:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.