# What is the largest distance that still guarantees a linear time distance search?

Suppose we have two sorted arrays A and B consisting of unique real numbers. We want to find all pairs of the form (a $\in$ A, b $\in$ B) such that, for some c $\in R+$, their absolute difference $\mid$a - b$\mid$ $\lt$ c.

If c is 0, we can linearly search the two sorted arrays for exact matches. If c is arbitrarily large, we need to return all pairs that exist between the two arrays, which is an $n^2$ search. My question is whether there exists a function $c_{max} = f(A, B)$ that, given the two arrays, finds the largest c for which all pairs with difference less than c can still be found in linear time.

This is a problem I've been thinking about while messing around with improving an algorithm, so I don't have the answer.

There's a straightforward algorithm for your original problem, based on a linear scan through the array with two pointers, one to $a$ and the other to the largest $b$ such that $|a-b|<c$. The running time will be linear in the number of pairs $a,b$ that need to be output.
So, this answers your question in the positive: if $c$ is small enough that the number of such pairs is $O(n)$, then the running time will be $O(n)$.
• Right, I agree with you. I guess a way to rephrase my question would be this: Does there exist a function such that, given A and B, it returns the largest c for which the number of such pairs is in $O(n)$? – ness_boy Sep 14 '17 at 14:19
• @AndrewDraganov, yes, there does - you just specified such a function! (Assuming we replace the asymptotic $O(n)$ with a concrete value.) – D.W. Sep 14 '17 at 15:35