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 Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

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

0

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?

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), ??

and if not O(n), ??

+1

it cant be so... Tightest upper bound is O(log n) only for sorted case..

Unsorted case tightest O(n)

Unsorted case tightest O(n)

0

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

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

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

0

yes . that is what i did bro. read the comments in https://gateoverflow.in/310907/made-easy-test-series-algorithm 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.

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

- All categories
- General Aptitude 1.8k
- Engineering Mathematics 7.3k
- Digital Logic 2.9k
- Programming & DS 4.9k
- Algorithms 4.3k
- Theory of Computation 6k
- Compiler Design 2k
- Databases 4.1k
- CO & Architecture 3.4k
- Computer Networks 4.1k
- Non GATE 1.4k
- Others 1.4k
- Admissions 596
- Exam Queries 577
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 18

49,532 questions

54,123 answers

187,319 comments

71,044 users