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

  • 5
    $\begingroup$ 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? $\endgroup$ Commented Aug 11, 2023 at 7:40
  • $\begingroup$ 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}$? $\endgroup$
    – Neal Young
    Commented Dec 13, 2023 at 16:04

2 Answers 2


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.

  • $\begingroup$ 3 should be check if $\text{Query}(x_{i+1}) > k(i+1) - x^2_{i+1}$ ? $\endgroup$ Commented Aug 11, 2023 at 17:55
  • $\begingroup$ Yes, that's correct. I fixed the typo. $\endgroup$
    – yangpliu
    Commented Aug 11, 2023 at 20:32
  • $\begingroup$ I wonder if one can adopt parametric search to avoid that $\epsilon$. $\endgroup$
    – Chao Xu
    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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.