The Gateway to Computer Science Excellence
+1 vote
132 views

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 (117k points) | 132 views
+1
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 < 6..so apply case 2..then you will go in next half.  Like this you can find A[i] =i if it exists.
0
@ankit here we need to check every element

right?

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) ??
+1
yes mam. It can be O(n) but question is about tightest upper bound.
+1

@ankitgupta.1729

thanks too good, got it :)

0
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).
0

@Arkaprava

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

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

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

1 Answer

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

mid=low+high/2

compare      (key > mid)

                 mid+1,high

                     (key<mid)

                low, mid-1
by (201 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,644 questions
56,531 answers
195,622 comments
101,346 users