210 views

.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 ??

| 210 views
0

@srestha

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?

+2
0
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), ??
0
How can it be O(log n) for unsorted array?
+1
it cant be so... Tightest upper bound is O(log n) only for sorted case..

Unsorted case tightest O(n)
0

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

@Satbir

tightest is always calculated based on WORST CASE.

0

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.

+2

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.

+1

yes I agree with you. my mistake. @Hirak

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

Right??

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

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

IF it is giving that array is sorted..

Then O(log n) will be correct answer.

by (93 points)