<p>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|&lt;c$.  The running time will be linear in the number of pairs $a,b$ that need to be output.</p>

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

CC BY-SA 3.0
2017-09-14T14:19:45.420Z
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)$?
Andrew Draganov
CC BY-SA 3.0
2017-09-14T15:35:33.523Z
@AndrewDraganov, yes, there does - you just specified such a function!  (Assuming we replace the asymptotic $O(n)$ with a concrete value.)
D.W.
CC BY-SA 3.0
2017-09-14T15:57:22.170Z
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.
Andrew Draganov
CC BY-SA 3.0
2017-09-14T16:14:34.137Z
@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.
D.W.
CC BY-SA 3.0
2017-09-13T21:51:03.430Z
2017-09-13T21:51:03.430Z
D.W.
<p>Suppose we have two sorted arrays <em>A</em> and <em>B</em> consisting of unique real numbers. We want to find all pairs of the form (<em>a</em> $\in$ <em>A</em>, <em>b</em> $\in$ <em>B</em>) such that, for some <em>c</em> $\in R+$, their absolute difference $\mid$<em>a - b</em>$\mid$ $\lt$ <em>c</em>.</p>

<p>If <em>c</em> is 0, we can linearly search the two sorted arrays for exact matches. If <em>c</em> 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.</p>

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

<cc.complexity-theory><search-problem>
What is the largest distance that still guarantees a linear time distance search?
Andrew Draganov
# What is the largest distance that still guarantees a linear time distance search?

(Asked by: username_0 on 2017-09-13)

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.

**Tags:** cc.complexity-theory, search-problem


---

## 1 answers

### Answer by username_1 on 2017-09-13. Score: 1

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|

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

> **Comments:**
> **username_0**: 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)$?  
> **username_1**: @AndrewDraganov, yes, there does - you just specified such a function!  (Assuming we replace the asymptotic $O(n)$ with a concrete value.)  
> **username_0**: 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.  
> **username_1**: @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.  

---

