Can I search two arrays for entries `a[i] + b[i] > N` faster than linear time?

Question

I have two sets of arrays, as and bs, all of length n. If I choose an a and a b, I know that a[i] <= N and b[i] <= N for all 0 <= i < n. What's the most efficient way to calculate whether a[i] + b[i] <= N for all i?

Currently, I'm simply looping through the arrays and comparing a[0] + b[0] <= N, a[1] + b[1] <= N etc. Obviously this is an O(n) approach.

Is there any way to pre-process the as and bs arrays so that the search for a sum a[i] + b[i] > N can be done faster than linear time?

Answer 1

If you can't preprocess, then O(n) is the best you can have. Proof is by contradicion: suppose you are given some algorithm which is better than O(n); it means that for some large n some indexes will be skipped (since the algorithm has better than linear time complexity). We can construct a counter example; let's run the algorithm for a large enough n

a[i] = 0,     for all i
b[i] = N - 1, for all i

if algorithm returns false (i.e. for some j a[j] + b[j] > N) it is incorrect. If algorithm returns true it skips some indexes, e.g. index k (since the algorithm is better than linear and n is large enough). So the counter example will be

a[i] = 0,     for all i, except k
b[i] = N - 1, for all i

a[k] = 2

the algorithm will return false (index k will be skipped, when all the rest values are the same as in the 1st run) which is incorrect now.

If you can preprocess a and b arrays, you can compute max = Max(a[i] + b[i]) and then return

max <= N

having O(1) time and space complexity

Answer 2

The other answer assumes unsorted arrays, however, I think it's good to mention the case where the array is sorted.

If both arrays are sorted, then the calculation is O(1), as we just need to check that the sum of the last elements meet the rule:

a[n-1] + b[n-1] <= N If this is met, then the rule is true for all indices.