C++ check of this condition in O(nlog(n)) time?

Question

Suppose you have a sorted vector {x_i}_i=1ⁿ whose elements are all positive and contain no tie (=no two elements in this vector are the same).

I'm looking for the smartest way to check that:

2x_i - x_j - x_k != 0 for all 1 <= i != j != k <= n.

I have a hunch that this could be done in time O(nlog n), or otherwise in better than naive time, perhaps using a strategy similar to what is developed in the answers to this question.

Recall that the entries of x are all positive and sorted so the entries of x_k+k_j are sorted as well.

P.S. Im looking for algorithmic/language agnostic ideas. The c++ tag is mainly there in case doing this requires taking advantage of some smart caching strategy.

Edit:

@liori makes a good point below, that finding the pair (j,k) for a given i is O(n), using an algorithm similar to what is done in the last iteration of this answer to a related question. The issue here is IMO whether it is possible to combine these many O(n) steps more efficiently than naively. For example, we can find the pair (j,k) for a given index i in time O(n). But do we need to consider again all the the entries j'<=j and k'<=k as candidates for the following index i'=i+1? Does these savings somehow add up?

Answer 1

Note that "sorted" doesn't help you, since comparison-based sorting can sort any list of n numbers in O(n log n) time.

I can't quite prove 3SUM-completeness for this problem, but this paper by Jeff Erickson proves that, in a restricted model of computation, no subquadratic algorithm for your problem exists. This is not quite an impossibility proof, but the model of computation Erickson uses allows all of the reasonable tricks I can think of. In particular, I doubt that anyone on this site is going to come up with an O(n log n) algorithm for your problem in the near future.

It may interest you that, in some models of computation permitting limited parallelism, there exists a subquadratic algorithm for 3SUM. I believe that this paper by Baran, Demaine, and Patrascu was the first to show this.

Answer 2

Quadratic time is possible with an algorithm as follows:

For every i∈{1, …, N}:

1. Let j=i-1, k=i+1.
2. If j<1 or k>N, stop.
3. Compute d=(x_i - x_j) - (x_k - x_i)
4. If d=0, stop.
5. If d<0, j--.
6. If d>0, k++.
7. Repeat from step 2.

This algorithm uses the fact that x_i must have a value that is equally as far from x_j (the x_i - x_j expression) as it is from x_k (x_k - x_i). Also, given the vector is sorted, the differences increase with increase in difference between indices.