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

  • $\begingroup$ 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)$? $\endgroup$ – ness_boy Sep 14 '17 at 14:19
  • $\begingroup$ @AndrewDraganov, yes, there does - you just specified such a function! (Assuming we replace the asymptotic $O(n)$ with a concrete value.) $\endgroup$ – D.W. Sep 14 '17 at 15:35
  • $\begingroup$ Yes, I am aware that such a function likely exists, and am more interested in the form that it takes. Given the values in A and B (and the time complexity n), what does the function look like that returns the maximum c? Do the means of A and B come into play? The variances? Something else? Things along those lines. Sorry if my initial question was too vague. $\endgroup$ – ness_boy Sep 14 '17 at 15:57
  • $\begingroup$ @AndrewDraganov, if you're asking about the mathematical function, you've already defined it. That's what it looks like. A function is just a mapping; it doesn't necessarily have to be in some algebraic form, or be limited to only using information like the variance. This doesn't sound like a research-level question about theoretical computer science. $\endgroup$ – D.W. Sep 14 '17 at 16:14

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.