in Algorithms retagged by
1,187 views
2 votes
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 retagged by
by
1.2k views

4 Comments

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

1 Answer

0 votes
0 votes

IF it is giving that array is sorted..

 

Then O(log n) will be correct answer.

Related questions