The Gateway to Computer Science Excellence
+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 by Active (3.6k points) | 208 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.

by (93 points)
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,833 questions
57,723 answers
107,785 users