Lower Bound for Sorted 2-Sum

Question

Given a sorted array of integers $x$ and a target value $t$, determine if there exists a pair $x_i, x_j \in x \wedge i \neq j$ such that $x_i + x_j = t$.

What is the lower bound for this problem?

---

I know for the generalized $k$-sum (unsorted) there is a lower bound of $\Omega(n^{\lceil \frac{k}{2}\rceil} )$. This would mean if the array were unsorted we could prove a lower bound of $\Omega(n)$. I would assume sorting it would give us some sort of extra information. I also haven't seen any lower bound claims of this problem so feel free to link a solution if one already exists.

It is relatively easy to show a lower bound of $\Omega(\log_2 n)$ using an adversary:

1. Create $x$ such that every sum of each pairs of integers is unique (hint: Fibonacci Numbers).

2. We also have that the target $t$ is larger than all values so no values can be preemptively discarded (hint: add a reasonable constant to all values).

Now we have $\frac{n(n-1)}{2}$ possible target values. Using an optimal binary search of these target values it takes $\Omega(\log_2 (n^2)) = \Omega(\log n)$. So it's easily lower bounded by $\log n$.

Although the algorithm can't necessarily perform an optimal binary search, because it takes at least $\Omega(n^2)$ to create all the unique sums of pairs. Unless it could figure out the median of all sums of pairs in less time than it takes to create them (another interesting question).

I would assume we can take advantage of this lack of knowledge in some way to establish a greater lower bound, possibly $\Omega(n)$. The standard algorithm to solve this takes $O(n)$ using two pointers. It does this because it's difficult to discard particular values without explicitly checking them. Any help would be greatly appreciated.

Answer 1

Consider the following problem I'll call check-for-ones (where it is easy to show a lower bound of $\Omega(n)$): given a binary array of length $n$, check if there are any 1s in this array. We'll reduce this problem to the sorted-2-sum problem, thereby showing that sorted-2-sum also should require $\Omega(n)$ time.

We need to be a bit careful what we mean by "reduce" here; the standard notion of polytime reduction is useless, and even a linear-time reduction doesn't say much since we can solve both problems trivially in linear-time. Our reduction will have the following property: it will reduce an instance $y$ of our check-for-ones problem to an instance $x$ of the sorted-2-sum problem such that for any index $i$, we can compute $x_i$ in time $O(1)$ given random access to $y$ (assuming that all word operations take $O(1)$ time).

Now, if you can solve sorted-2-sum in $O(t)$ time, you read in at most $O(t)$ values $x_i$, and each $x_i$ can be computed from associated $y_j$ in $O(1)$ time, and therefore you can also solve check-for-ones in $O(t)$ time.

Here is the reduction. Let the array $x$ have length $2n$. When reading a value $x_i$ proceed as follows:

• If $1 \leq i\leq n$, let $x_i = -100(n+1-i)$

• If $n < i \leq 2n$, let $x_i = 100(i-n) + y_{i-n}$

Now, the equation $x_{j} + x_{k} = 1$ has a solution iff there exists a $y_{i} = 1$ (in particular, $(j,k)$ must be a pair of the form $(n-a, n+a-1)$).

An example might help as well, let $y$ be the following:

$$y = \{0,0,1,0\}$$

We then have that $x$ (if we were to have read $O(n)$ values) would be:

$$x = \{-400, -300, -200, -100, 100, 200, 301, 400\}$$

We can see how $x_j + x_k = 1 \Leftarrow \Rightarrow \exists y_i =1 \in y$. In our case, $-300 + 301 = 1$ implies $y_3 = 1$.