Log In
2 votes

.Given an array of distinct integers A[1, 2,…n]. Find the tightest upper bound to check the existence of any index i for which A[i]=i.

Ans should be O(log n) right by doing binary search ??

in Algorithms 457 views


I remember that u have asked a same question few days ago, but couldn't find its link...

The answer will be O(log n) right?

The way they havr framed the question i think they are taking about sorted array..if sorted O(log n) right?

and if not O(n), ??
How can it be O(log n) for unsorted array?
it cant be so... Tightest upper bound is O(log n) only for sorted case..

Unsorted case tightest O(n)
why? please explain.

what is the best case among all the worst cases ?

here it is not mentioned whether array is sorted or unsorted so we can take best among the worst cases as O(log n).
take this array--> [1,2,90,100,3,5,4,8]

write an algo in O(log n) that checks the condition of the question..


tightest is always calculated based on WORST CASE.


yes . that is what i did bro. read the comments in and then read my comments again.

for an algo if O(n^2) is the worst case then O(n^3) will also be worst case but we have to select O(n^2) as tightest upper bound.


yeah, that is right O($n^2$)

but see for this case if the array is unsorted, like this [1,2,90,100,3,5,4,8] we need O(n) we can never solve it in O(log n),

say for quicksort we can solve it in O(nlogn),but that is the average case, it is not the tightest upper bound, in worst quicksort can go to O(n^2), that is why O(n^2) is the tightest UB and O(n^3) O(n^4) is also possible,

similarly for our problem we can solve it in O(log n) given it is sorted, but if unsorted we need O(n). So O(n) is the tightest upper bound.

The above link that Srestha has provided clearly states that the array is sorted, hence tighest bound was O(logn) but it is not so for our case.


yes I agree with you. my mistake. @Hirak

Not a problem, brother.. :)
It could be done in $O\left ( n\log n \right )$ time too.


So tightest upper bound will be $O\left ( n\log n \right )+O\left ( \log n \right )=O\left ( n\log n \right )$

why will we go for O(n log n) when we can solve it in O(n) ?
put Merge Sort for sorting all elements. Then found element in log n time
but O(n) is better than O(n log n) so we should go with O(n) right ?
yes, chking every element can do it

1 Answer

0 votes

IF it is giving that array is sorted..


Then O(log n) will be correct answer.

Related questions

1 vote
2 answers
Let $A$ be an array of $31$ numbers consisting of a sequence of $0$’s followed by a sequence of $1$’s. The problem is to find the smallest index $i$ such that $A[i]$ is $1$ by probing the minimum number of locations in $A$. The worst case number of probes performed by an optimal algorithm is $2$ $4$ $3$ $5$
asked Mar 30, 2020 in Algorithms Lakshman Patel RJIT 337 views
0 votes
1 answer
Which of the following search method takes less memory ? Depth-first search Breadth-first search Linear search None of the above
asked Mar 2, 2018 in Unknown Category gatecse 149 views