Given an unsorted array A, check if A[i] = i exists efficiently

Question

Given array A, check if A[i] = i for any i exists.

I'm supposed to solve this faster than linear time, which to me seems impossible. The solution I came up with is to first sort the array in n*log(n) time, and then you can easily check faster than linear time. However, since the array is given unsorted I can't see an "efficient" solution?

Answer 1

You can't have a correct algorithm with better than O(N) complexity for an arbitrary (unsorted) array.

Suppose you have the solution better than O(N). It means that the algorithm has to omit some items of the array since scanning all the items is O(N).

Construct A such that A[i] != i for all i then run the algorithm. Let A[k] be the item which has been omitted. Assign k to A[k], run the algorithm again - it'll return no such items when k is expected.

Answer 2

You'll get O(log n) with a parallel algorithm (you didn't restrict that). Just start N processors in ld(N) steps and let them check the array items in parallel.