Given a sorted array of distinct integer $A[1,2.....n]$ the tightest upper bound to check the existence of any index $I$, for which $A[I]=I$ is equal to _______________ ?

I thought here answer that mean time complexity will be $O(1)$, because directly getting the searching index and then checking if $A[I]=I$, but answer given as $O(log n)$.

Please help me out, which will be correct answer?

  • $\begingroup$ You have to find i. $\endgroup$ – gnasher729 Apr 28 '19 at 14:40

If the array had $A[i]=i, \forall{i}$, then the complexity would have been $\theta(1)$ as then all we need to check whether the length of the array is greater than the element or not. If it's greater we have the element, else we haven't.

But the array isn't like that. Array could be like $1,3,4,8,9,12$ as well.

The question is asking to find an element $A[i]$ in the sorted list which is situated at the index $i$.

The algorithm to find such element is mere a slight modification of binary search where you update low & high based on $i<A[i]$ - if it's true update high=mid-1 else if $i>A[i]$ update low=mid+1. The complexity is indeed $\theta(log_2n)$

  • $\begingroup$ Is binary search always take an element a[I]=I?? ok, tell me one thing , if in this algorithm, I want T.C.=O(1), what modification needed for this code? $\endgroup$ – Srestha Apr 28 '19 at 9:15
  • $\begingroup$ @Srestha You can't achieve in $O(1)$ time. E.g, 1,4,6,9,12 (index starting with 1) $\endgroup$ – Mr. Sigma. Apr 28 '19 at 11:41
  • $\begingroup$ Mr. Sigma, I have not got the point. Here it is told a[I]=I, that means a[1]=1, a[2]=2,a[3]=3......only this type of sequence possible here. Then how r u telling a[1]=1,a[2]=4, a[3]=6 .... is a possible sequence. $\endgroup$ – Srestha Apr 28 '19 at 12:48
  • $\begingroup$ @Srestha Your question specifies that the input is a sorted array of distinct integers - it does not specify that, in the input, $A[i] = i$. If this is the case you should update your question. However, this would make the problem trivial. $\endgroup$ – AcId Apr 28 '19 at 13:04
  • 1
    $\begingroup$ @Srestha You have understood the question wrongly. Question involving $A[i]=i, \forall{i}$ would be very trivial. $\endgroup$ – Mr. Sigma. Apr 28 '19 at 13:58

Take the hints. The integers can be positive or negative, but they are distinct. The array is sorted, which usually means a1 ≤ a2 ≤ a3 ... But the are distinct, so a1 < a2 < a3 < ... And they are integers, so they are at least 1 apart. So we have a2 ≥ a1 + 1, a3 ≥ a2 + 1, a4 ≥ a3 + 1 and so on. What does that mean for ai - i?

(If you figure that out, the solution is trivial).

  • $\begingroup$ Plz check my above comment. I understand everything except , what a[I]=I is doing? Is it checking every I or it checking a particular I? $\endgroup$ – Srestha Apr 28 '19 at 14:59
  • $\begingroup$ Srestha, you are supposed to either find an i such that a[i] = i or demonstrate that such an i does not exist. You could check is a[1]=1? Is a[2]=2? And so on but that is slow. $\endgroup$ – gnasher729 Apr 28 '19 at 15:19
  • $\begingroup$ "either find an i such that a[i] = i or demonstrate that such an i does not exist. "-if I does not exists, we have to check every I in O(n) time. Is not it? $\endgroup$ – Srestha Apr 28 '19 at 15:27
  • $\begingroup$ I am getting either O(1) time , or O(n) time, but not getting O(log n), because it is not checking only a element, but it is checking element with an index $\endgroup$ – Srestha Apr 28 '19 at 15:30

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.