Finding an element in array, whose index number and element value same
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 &amp; high based on $i&lt;A[i]$ - if it's true update high=mid-1 else if $i&gt;A[i]$ update low=mid+1.  The complexity is indeed $\theta(log_2n)$