Lower-bound of a decision problem [closed]

What's the lower-bound of the decision problem that decides:

Whether there is at least one element A[i] such that A[i] = i in a sorted array A of non-negtive integers? (An example is A = {0,1,1,3,4,4,5}.)

Is there any sub-linear deterministic algorithm can solve the problem?

-

closed as off-topic by Yuval Filmus, JɛﬀE, Hsien-Chih Chang 張顯之, Robin Kothari, KavehApr 29 '14 at 21:50

This question appears to be off-topic. The users who voted to close gave this specific reason:

• "Your question does not appear to be a research-level question in theoretical computer science. For more information about the scope, please see help center. Your question might be suitable for Computer Science which has a broader scope." – Yuval Filmus, JɛﬀE, Hsien-Chih Chang 張顯之, Robin Kothari, Kaveh
If this question can be reworded to fit the rules in the help center, please edit the question.

There is no sub-linear algorithm for it, assuming the array may have duplicates as in your example. The following shows that any algorithm must read all of $|A|$'s values.

Assume that there's sub linear algorithm $Alg$ that decides it.

Define an array $A$ by $A_k = k+1$.

Since $alg$ is sublinear, there has to be some cell of $A$ he didn't query. Denote such cell's index by $i$.

Define $B_k = \left\{ \begin{array}{ll} k+1 & \mbox{if } k \neq i \\ i & \mbox{if } k = i \\ \end{array} \right.$

Note since $Alg$ doesn't read cell $i$, it will answer the same for both $A$ and $B$, but obviously one of these answers is wrong..

-
Are you taking into the account that fact the array sorted? –  bagaria Apr 28 '14 at 11:49
@Bagaria - Yes, $A$ is sorted by my construction, and there's a single value which may appear twice. –  R B Apr 28 '14 at 11:51

I dont have a complete solution. But for the case when the elements in the array are strictly increasing, one can find the solution in $\log(n)$ time.

Solution

Let $B[i] = A[i] - i$

Now search for element $0$ in $B$ using binary search.

Proof : For the above algorithm to work, we need to prove that $B$ is also sorted. $$A[i] < A[i+1]\\ \text{thus we have } A[i] \leq A[i+1] - 1\\ A[i] - i \leq A[i+1] - (i + 1)\\ B[i] \leq B[i+1]$$

EDIT 1 This algorithm doesnt explicitly evaluate the matrix $B$. It uses the definition $B[i] = A[i] - i$ whenever required.

EDIT 2 The restriction $A$ has to satisfy for the above case is $A[i+j] - A[i] \geq j \; \forall j > 0$. We could relax the restriction to the following $$A[j+i] - A[i] \geq i \; \forall j > f(n)$$ where $f(n)$ is a sublinear function in $n$.

The above restriction would ensure that $B[i+j] \geq B[j] \;\forall j > f(n)$. Now we can use a simple variant of binary search for obtain the solution in $O(f(n)*\log n)$ time.

-
My answer above shows that even if a single number is allowed to appear only twice, you can't decide the problem with $\leq n-1$ queries of A's value.. –  R B Apr 28 '14 at 13:29
Even for strictly increasing array your algorithm is $\Omega(n)$ not $O(\log n)$ because you have to read whole $A$ to fill $B$. –  Saeed Apr 28 '14 at 14:53
@Saeed - I don't think you actually fill $B$, but rather infer $B_i$'s value by a single access to $A$ whenever the algorithm makes a query. –  R B Apr 28 '14 at 15:10
@RB, Actually by current algorithm he searches on B not A (as stated and written right now, or I misread it), but you are also right. –  Saeed Apr 28 '14 at 15:24
@RB: My solution to the case when each element being repeated sub-linear number of times was wrong. Apologies for the same. –  bagaria Apr 28 '14 at 16:20