<p>Here is a different algorithm that outputs a <span class="math-container">$1-\epsilon$</span> multiplicative approximation in time <span class="math-container">$O(n \log^2(n)/\epsilon)$</span>, but works for more general settings, (if we want to find the maximum of <span class="math-container">$\frac{f(|x_j - x_i|)}{j-i}$</span> for any increasing function <span class="math-container">$f(t)$</span> such as <span class="math-container">$f(t) = t$</span>). The computational model is that two real numbers can be compared in <span class="math-container">$O(1)$</span> time.</p>
<p>Subroutine: Create a data structure <span class="math-container">$D$</span> which takes in a contiguous interval <span class="math-container">$I = [a,b] = \{a, a+1, \ldots, b\}$</span> and outputs <span class="math-container">$i,j = \text{argmax}_{i,j \in I} |x_j - x_i|$</span>.</p>
<p>Assume the subroutine exists for now. The idea is now to try all possible values of <span class="math-container">$j-i$</span> rounded to the nearest power of <span class="math-container">$(1+\epsilon)$</span>. For every fixed power <span class="math-container">$(1+\epsilon)^k$</span>, we can invoke the subroutine <span class="math-container">$O(n)$</span> times to find the largest value of <span class="math-container">$(x_j - x_i)^2$</span>, conditioned on <span class="math-container">$j-i \approx (1+\epsilon)^k$</span>. This gives the desired approx. guarantees.</p>
<p>In more detail, we iterate over <span class="math-container">$ t = 1, \lfloor (1+\epsilon) \rfloor, \lfloor(1+\epsilon)^2 \rfloor, \lfloor(1+\epsilon)^3\rfloor, \ldots, $</span>. For a fixed power, we invoke the subroutine at most <span class="math-container">$n$</span> times on the intervals <span class="math-container">$[1, t+1], [2, t+2], \ldots, $</span>.  Now let <span class="math-container">$i^* &lt; j^*$</span> denote the OPT pair and suppose <span class="math-container">$(1+\epsilon)^{t^*}$</span> is the nearest power larger than <span class="math-container">$j^*- i^*$</span>. We return some pair <span class="math-container">$j' &gt; i'$</span> when we query <span class="math-container">$[i^*, i^* + (1+\epsilon)^{t^*}]$</span> and <span class="math-container">$(x_j' - x_i')^2 \ge (x_j^* - x_i^*)^2$</span>, <span class="math-container">$(j^* - i^*) \ge (1-\epsilon)(j' - i')$</span>. In other words, we find a value that is at least <span class="math-container">$(1-\epsilon)$</span>OPT.</p>
<p>Thus it remains to analyze the runtime of the subroutine. We show that we can construcut such a datstructure in <span class="math-container">$O(n \log n)$</span> time where each query times <span class="math-container">$O(\log n)$</span> time.</p>
<p><span class="math-container">$D$</span> is simply a balanced binary tree over the interval <span class="math-container">${1, \ldots, n}$</span>  where each node stores the min and max <span class="math-container">$x_i$</span> over all <span class="math-container">$i$</span> that are `covered' by the node. To answer any given query interval <span class="math-container">$I$</span>, we can break it down into <span class="math-container">$O(\log n)$</span> contiguous intervals <span class="math-container">$I = I_1 \cup I_2 \ldots$</span> (this is a standard procedure for ex. interval trees), query eeach of them, and just return the max - min over all <span class="math-container">$x$</span>'s returned.</p>

CC BY-SA 4.0
2023-12-10T05:23:17.230Z
2023-12-10T05:23:17.230Z
Sandeep Silwal
<p>Getting an algorithm which runs in time <span class="math-container">$O(n \log n \log(1/\epsilon))$</span> for a <span class="math-container">$\epsilon$</span>-approximation is pretty standard. We will require the following data structure, which I'll call a ``line container''.</p>
<p><strong>Line container:</strong> There is a data structure that maintains a set <span class="math-container">$\mathcal{L}$</span> of lines <span class="math-container">$L: \mathbb{R} \to \mathbb{R}$</span>, and supports the following operations, in amortized time <span class="math-container">$O(\log n)$</span>.</p>
<ul>
<li>Insert(<span class="math-container">$L$</span>): Insert a line <span class="math-container">$L$</span> into <span class="math-container">$\mathcal{L}$</span>.</li>
<li>Query(<span class="math-container">$x \in \mathbb{R}$</span>): Return <span class="math-container">$\max_{L \in \mathcal{L}} L(x)$</span>.</li>
</ul>
<p>By binary search, it suffices to check for each real number <span class="math-container">$k &gt; 0$</span>, whether there is a pair <span class="math-container">$i &lt; j$</span> such that <span class="math-container">$(x_j-x_i)^2/(j-i) &gt; k$</span>. This rearranges to <span class="math-container">$-2x_i \cdot x_j + x_i^2 + ki &gt; kj - x_j^2$</span>. This suggests the following algorithm.</p>
<ol>
<li>For <span class="math-container">$i = 1, 2, \dots, n-1$</span>.</li>
<li>Insert the line <span class="math-container">$L_i(x) = -2x_i \cdot x + x_i^2 + ki$</span> into <span class="math-container">$\mathcal{L}$</span>.</li>
<li>Check if Query(<span class="math-container">$x_{i+1}$</span>) <span class="math-container">$&gt; k(i+1) - x_{i+1}^2$</span>.</li>
</ol>
<p><strong>Sketch for construction of line container:</strong> For any set <span class="math-container">$\mathcal{L}$</span>, the function <span class="math-container">$f(x) = \max_{L \in \mathcal{L}} L(x)$</span> is some upper convex hull-like object. When a line is inserted, binary search to find where it intersects the convex hull, and update the convex hull. This is efficient because a line intersects this convex hull in at most two points.</p>

CC BY-SA 4.0
2023-08-11T17:55:39.430Z
3 should be check if $\text{Query}(x_{i+1}) > k(i+1) - x^2_{i+1}$ ?
Timon Knigge
CC BY-SA 4.0
2023-08-11T20:32:17.913Z
Yes, that's correct. I fixed the typo.
yangpliu
CC BY-SA 4.0
2023-12-12T16:36:58.593Z
I wonder if one can adopt parametric search to avoid that $\epsilon$.
Chao Xu
CC BY-SA 4.0
2023-08-11T15:02:32.057Z
2023-08-11T20:32:48.440Z
2023-08-11T20:32:48.440Z
yangpliu
<p>Can it be done in linear or at least subquadratic time?</p>

CC BY-SA 4.0
2023-08-11T07:40:03.907Z
Can you format your problem and give more details/context? Also, any bounds on $x_i$? Are they non-negative? Is weakly polynomial (i.e sth like $O(n \log M)$ where M is the maximum $x_i$ useful?
user3508551
CC BY-SA 4.0
2023-12-13T16:04:20.390Z
Can anyone find a sub-quadratic-time exact algorithm for the following (perhaps easier) decision problem?  _Given a sequence $x_1, x_2, \ldots, x_n$ of rationals in increasing order, do there exist $i, j$ with $i < j$ such that $x_j - x_i < \sqrt{j-i}$?_
Neal Young
<ds.algorithms>
Given real numbers $x_1,...,x_n$ , find the maximum of $ \frac{(x_j-x_i)^2}{j-i}$
Scott Aaronson
# Given real numbers $x_1,...,x_n$ , find the maximum of $ \frac{(x_j-x_i)^2}{j-i}$

(Asked by: username_0 on 2023-08-11)

Can it be done in linear or at least subquadratic time?

**Tags:** ds.algorithms
> **Comments:**
> **username_1**: Can you format your problem and give more details/context? Also, any bounds on $x_i$? Are they non-negative? Is weakly polynomial (i.e sth like $O(n \log M)$ where M is the maximum $x_i$ useful?  
> **username_2**: Can anyone find a sub-quadratic-time exact algorithm for the following (perhaps easier) decision problem?  _Given a sequence $x_1, x_2, \ldots, x_n$ of rationals in increasing order, do there exist $i, j$ with $i < j$ such that $x_j - x_i < \sqrt{j-i}$?_  

---

## 2 answers

### Answer by username_4 on 2023-08-11. Score: 10 | Accepted answer

Getting an algorithm which runs in time $O(n \log n \log(1/\epsilon))$ for a $\epsilon$-approximation is pretty standard. We will require the following data structure, which I'll call a ``line container''.

**Line container:** There is a data structure that maintains a set $\mathcal{L}$ of lines $L: \mathbb{R} \to \mathbb{R}$, and supports the following operations, in amortized time $O(\log n)$.

* Insert($L$): Insert a line $L$ into $\mathcal{L}$.
* Query($x \in \mathbb{R}$): Return $\max\_{L \in \mathcal{L}} L(x)$.

By binary search, it suffices to check for each real number $k > 0$, whether there is a pair $i < j$ such that $(x\_j-x\_i)^2/(j-i) > k$. This rearranges to $-2x\_i \cdot x\_j + x\_i^2 + ki > kj - x\_j^2$. This suggests the following algorithm.

1. For $i = 1, 2, \dots, n-1$.
2. Insert the line $L\_i(x) = -2x\_i \cdot x + x\_i^2 + ki$ into $\mathcal{L}$.
3. Check if Query($x\_{i+1}$) $> k(i+1) - x\_{i+1}^2$.

**Sketch for construction of line container:** For any set $\mathcal{L}$, the function $f(x) = \max\_{L \in \mathcal{L}} L(x)$ is some upper convex hull-like object. When a line is inserted, binary search to find where it intersects the convex hull, and update the convex hull. This is efficient because a line intersects this convex hull in at most two points.

> **Comments:**
> **username_5**: 3 should be check if $\text{Query}(x_{i+1}) > k(i+1) - x^2_{i+1}$ ?  
> **username_4**: Yes, that's correct. I fixed the typo.  
> **username_6**: I wonder if one can adopt parametric search to avoid that $\epsilon$.  

---

### Answer by username_3 on 2023-12-10. Score: 1

Here is a different algorithm that outputs a $1-\epsilon$ multiplicative approximation in time $O(n \log^2(n)/\epsilon)$, but works for more general settings, (if we want to find the maximum of $\frac{f(|x\_j - x\_i|)}{j-i}$ for any increasing function $f(t)$ such as $f(t) = t$). The computational model is that two real numbers can be compared in $O(1)$ time.

Subroutine: Create a data structure $D$ which takes in a contiguous interval $I = [a,b] = \{a, a+1, \ldots, b\}$ and outputs $i,j = \text{argmax}\_{i,j \in I} |x\_j - x\_i|$.

Assume the subroutine exists for now. The idea is now to try all possible values of $j-i$ rounded to the nearest power of $(1+\epsilon)$. For every fixed power $(1+\epsilon)^k$, we can invoke the subroutine $O(n)$ times to find the largest value of $(x\_j - x\_i)^2$, conditioned on $j-i \approx (1+\epsilon)^k$. This gives the desired approx. guarantees.

In more detail, we iterate over $ t = 1, \lfloor (1+\epsilon) \rfloor, \lfloor(1+\epsilon)^2 \rfloor, \lfloor(1+\epsilon)^3\rfloor, \ldots, $. For a fixed power, we invoke the subroutine at most $n$ times on the intervals $[1, t+1], [2, t+2], \ldots, $. Now let $i^\* < j^\*$ denote the OPT pair and suppose $(1+\epsilon)^{t^\*}$ is the nearest power larger than $j^\*- i^\*$. We return some pair $j' > i'$ when we query $[i^\*, i^\* + (1+\epsilon)^{t^\*}]$ and $(x\_j' - x\_i')^2 \ge (x\_j^\* - x\_i^\*)^2$, $(j^\* - i^\*) \ge (1-\epsilon)(j' - i')$. In other words, we find a value that is at least $(1-\epsilon)$OPT.

Thus it remains to analyze the runtime of the subroutine. We show that we can construcut such a datstructure in $O(n \log n)$ time where each query times $O(\log n)$ time.

$D$ is simply a balanced binary tree over the interval ${1, \ldots, n}$ where each node stores the min and max $x\_i$ over all $i$ that are `covered' by the node. To answer any given query interval $I$, we can break it down into $O(\log n)$ contiguous intervals $I = I\_1 \cup I\_2 \ldots$ (this is a standard procedure for ex. interval trees), query eeach of them, and just return the max - min over all $x$'s returned.


---

