1
$\begingroup$

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?

$\endgroup$

2 Answers 2

9
$\begingroup$

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

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

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.

$\endgroup$
5
  • $\begingroup$ 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.. $\endgroup$
    – R B
    Commented Apr 28, 2014 at 13:29
  • $\begingroup$ Even for strictly increasing array your algorithm is $\Omega(n)$ not $O(\log n)$ because you have to read whole $A$ to fill $B$. $\endgroup$
    – Saeed
    Commented Apr 28, 2014 at 14:53
  • $\begingroup$ @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. $\endgroup$
    – R B
    Commented Apr 28, 2014 at 15:10
  • $\begingroup$ @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. $\endgroup$
    – Saeed
    Commented Apr 28, 2014 at 15:24
  • $\begingroup$ @RB: My solution to the case when each element being repeated sub-linear number of times was wrong. Apologies for the same. $\endgroup$ Commented Apr 28, 2014 at 16:20

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