# Given real numbers $x_1,...,x_n$ , find the maximum of $\frac{(x_j-x_i)^2}{j-i}$

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

• 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? Commented Aug 11, 2023 at 7:40
• 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}$? Commented Dec 13, 2023 at 16:04

## 2 Answers

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.

• 3 should be check if $\text{Query}(x_{i+1}) > k(i+1) - x^2_{i+1}$ ? Commented Aug 11, 2023 at 17:55
• Yes, that's correct. I fixed the typo. Commented Aug 11, 2023 at 20:32
• I wonder if one can adopt parametric search to avoid that $\epsilon$. Commented Dec 12, 2023 at 16:36

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.