The Gateway to Computer Science Excellence
+1 vote

Given a sorted array of distinct integer $A\left [ 1,2,....n \right ]$, 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?

in Algorithms by Veteran (119k points) | 149 views
ma'am, how it can be O(1).

Suppose, there are 13 elements in  array A like :-

A[0] = -15

A[1] = -13

A[2] = -11

A[3] = -8

A[4] = -7

A[5]= -3
mid1= A[6]= -2

A[7] = 0
A[8] = 2

mid2=A[9] = 7

A[10]= 9

mid3 = A[11]= 11

A[12]= 55

Since, array is sorted. So, 1st think about binary search. suppose mid means middle. Now, consider cases like :-

1)  If A[mid] > mid then possibility of A[i] = i will be in the previous half from A[mid].
2) if A[mid] < mid then possibility of A[i] =i will be in next half from A[mid].
3) if A[mid] = mid then you don't have to do anything because your objective is already completed.
Now,  if you apply it in above example then first we check middle element i.e. A[mid1] = -- 2 and mid1 is 6.  so here,  - 2 < apply case 2..then you will go in next half.  Like this you can find A[i] =i if it exists.
@ankit here we need to check every element


We donot know if any element is matching as A[i]=i

otherwise not matching

We have to check each and every element. So, then why not O(n) ??
yes mam. It can be O(n) but question is about tightest upper bound.


thanks too good, got it :)

Sorry to say ankitgupta.1729 . But it can never be O(n). Because we are discarding one half of our search space at every instant , the recurrence is of the form T(n)=T(n/2)+c . The solution is O(logn).


it can be O(n) by checking each element with its index but one better algo will give O(lgn) which I mentioned above. 

In this the lower bound would be O(1) right ?

since first element could be the answer.
how can lower bound be of big-oh?
oh my mistake it should be $\Omega$(1) right ?

1 Answer

0 votes
using binary search it will take O(logn)


compare      (key > mid)



                low, mid-1
by (211 points)

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,834 questions
57,750 answers
108,169 users