<p>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.</p>

<p>Assume that there's sub linear algorithm $Alg$ that decides it.</p>

<p>Define an array $A$ by $A_k = k+1$.</p>

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

<p>Define $B_k = \left\{
 \begin{array}{ll}
  k+1  &amp; \mbox{if } k \neq i \\
  i &amp; \mbox{if } k = i \\
 \end{array}
\right.$</p>

<p>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..</p>

CC BY-SA 3.0
2014-04-28T11:49:38.627Z
Are you taking into the account that fact the array sorted?
Vivek Bagaria
CC BY-SA 3.0
2014-04-28T11:51:34.777Z
@Bagaria - Yes, $A$ is sorted by my construction, and there's a single value which may appear twice.
R B
CC BY-SA 3.0
2014-04-28T11:43:47.540Z
2014-04-29T19:22:07.033Z
2014-04-29T19:22:07.033Z
R B
<p>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.</p>

<p><strong>Solution</strong></p>

<p>Let $B[i] = A[i] - i$</p>

<p>Now search for element $0$ in $B$ using binary search.</p>

<p><strong>Proof :</strong>
For the above algorithm to work, we need to prove that $B$ is also sorted.
$$A[i] &lt; 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]
$$</p>

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

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

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

CC BY-SA 3.0
2014-04-28T13:29:20.203Z
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
CC BY-SA 3.0
2014-04-28T14:53:30.113Z
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
CC BY-SA 3.0
2014-04-28T15:10:26.820Z
@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
CC BY-SA 3.0
2014-04-28T15:24:33.010Z
@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
CC BY-SA 3.0
2014-04-28T16:20:14.527Z
@RB: My solution to the case when each element being repeated sub-linear number of times was wrong. Apologies for the same.
Vivek Bagaria
CC BY-SA 3.0
2014-04-28T11:40:48.737Z
2014-04-29T04:15:22.720Z
2014-04-29T04:15:22.720Z
Vivek Bagaria
<p>What's the lower-bound of the decision problem that decides:</p>

<p>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}.)</p>

<p>Is there any sub-linear deterministic algorithm can solve the problem?</p>

<complexity-classes><time-complexity>
Lower-bound of a decision problem
aldrich
# Lower-bound of a decision problem

(Asked by: username_0 on 2014-04-28)

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?

**Tags:** complexity-classes, time-complexity


---

## 2 answers

### Answer by username_1 on 2014-04-28. Score: 9

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..

> **Comments:**
> **username_2**: Are you taking into the account that fact the array sorted?  
> **username_1**: @Bagaria - Yes, $A$ is sorted by my construction, and there's a single value which may appear twice.  

---

### Answer by username_2 on 2014-04-28. Score: 2

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.

> **Comments:**
> **username_1**: 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..  
> **username_3**: Even for strictly increasing array your algorithm is $\Omega(n)$ not $O(\log n)$ because you have to read whole $A$ to fill $B$.  
> **username_1**: @username_3 - 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.  
> **username_3**: @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.  
> **username_2**: @RB: My solution to the case when each element being repeated sub-linear number of times was wrong. Apologies for the same.  

---

