1
$\begingroup$

Recently i got a question in one of my exams about asking for an algorithm which searches an element in a sorted array such that $A[i] = i$. My algorithm was based on binary search and did a $O (\log n)$ order of comparisons. The other part of question demanded to prove there exists no other algorithm which does better than this. I tried to design an adversarial argument but it didn't seem to go in the correct direction. How can one go about proving this with an adversary argument , if one exists. Other approaches to proving this are also welcome. My algorithm works as follows :

Search(A , start , end)
  Find mid
  if A[mid] > mid // the element with A[i] = i cannot exist in A [mid ... end]
    Search (A,start, mid-1)
  else if A[mid] < mid // the element with A[i] = i cannot exist in A [start... mid]
    Search(A,mid+1,end)
  else if(A[mid] = mid)
    return A[mid];
  else 
    return false;
end

Edit: edit contains my algorithm. Kindly forgive any typesetting errors

$\endgroup$
  • $\begingroup$ Notice that if we construct a new array $B[i] = A[i]-i$ then the problem is equivalent to finding an element of the array equal to $0$ (which reduces the problem to simply proving that binary search is the most optimal for finding a specific element in an array) $\endgroup$ – cirpis Sep 10 '17 at 5:17
  • $\begingroup$ @cirpis the algorithm described by you is a correct approach but this doesn't help me see why an algorithm cannot exist which uses less comparisons than binary search $\endgroup$ – Shubham Singh rawat Sep 10 '17 at 5:20
  • 1
    $\begingroup$ (If you don't insert a space before punctuation marks (argument , if), the mark never gets wrapped to a line different from what it terminates.) I tried to design an adversarial argument but it didn't seem to go in the correct direction. Show what you tried! $\endgroup$ – greybeard Sep 10 '17 at 5:23
  • $\begingroup$ Could you, at least, describe your algorithm? First, we should be sure that your algorithm is correct. $\endgroup$ – fade2black Sep 10 '17 at 5:24
  • 1
    $\begingroup$ I edited your pseudocode, please check it. Your previous edit made it unreadable. $\endgroup$ – fade2black Sep 10 '17 at 5:49
4
$\begingroup$

Notice that the index of the element of the array requires $\Omega(\log(n))$ bits to represent. This means that there can be no better algorithm than $O(\log(n))$ to find this index.

Edit: To elaborate a bit, what you have is a binary search algorithm which works in $O(\log(n))$. What you want to prove is that any other algorithm for the same problem will work in no less than $O(\log(n))$. The proof involves information theorethic reasoning, since storing $n$ different numbers (the indices of the array) requires each to be represented by no less than $\log(n)$ bits. Now we can see, that in order for you to output/write the solution you need $\Omega(\log(n))$ bits, and you cannot do away with less (we can apply the same reasoning to comparisons since we need to compare $\log(n)$ bits to deduce whether one number is less than the other if they are the same on all but the last bit) This means that any algorithm will need atleast $O(\log(n))$ operations to produce output.

Now, obviously, since you have produced an algorithm working in $O(\log(n))$ then the bound is sharp.

to answer your question in the comment to this answer:

this information of log n bits on index is valid on unsorted array as well? why do we not have an algorithm to search an unsorted array in log n time? kindly elaborate whether or not is this valid for both ordered and un-ordered arrays?

while this is true for both unsorted and sorted arrays, it merely specifies a lower bound on the complexity of algorithms. This means that no algorithm can do better than $O(\log(n))$. It does not guarantee that there exists one though.

In an unordered array there are extra complexities that arrise, which prevent an $O(\log(n))$ solution. So we might say that the $\Omega(\log(n))$ is not sharp in this case since there does not exist an $O(\log(n))$ algorithm which could solve this problem for an unsorted array.

If we were to find a sharp lower bound for the unsorted array problem then we would need to use different assumptions and conduct a different analysis.

An important thing to realise is that this is all dependent on the underlying model of computations used. Is it assumed that comparisons take $O(1)$? How about writing a number to memory? If this is not defined then estimating complexity is tricky to say the least.

$\endgroup$
  • $\begingroup$ this information of log n bits on index is valid on unsorted array as well? why do we not have an algorithm to search an unsorted array in log n time? kindly elaborate whether or not is this valid for both ordered and un-ordered arrays? $\endgroup$ – Shubham Singh rawat Sep 10 '17 at 5:39
  • $\begingroup$ $\Omega(\log{n})$ bits are needed at least to write/output the index. $\endgroup$ – fade2black Sep 10 '17 at 6:43
  • 1
    $\begingroup$ @ShubhamSinghrawat, because there are no hints in unsorted array that will help you to find element in log time. Searching in unsorted array in log time can be done non-deterministically, but not deterministically. $\endgroup$ – rus9384 Sep 10 '17 at 12:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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