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 ?? Algorithms algorithms array searching vani-booklet + – Hirak asked May 21, 2019 • retagged Jul 8, 2022 by Lakshman Bhaiya Hirak 1.3k views answer comment Share Follow See all 18 Comments See all 18 18 Comments reply Hirak commented May 21, 2019 reply Follow Share @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? 0 votes 0 votes srestha commented May 21, 2019 reply Follow Share https://gateoverflow.in/310907/made-easy-test-series-algorithm 2 votes 2 votes Hirak commented May 21, 2019 reply Follow Share 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 votes 0 votes Hirak commented May 21, 2019 reply Follow Share How can it be O(log n) for unsorted array? 0 votes 0 votes Hirak commented May 21, 2019 reply Follow Share it cant be so... Tightest upper bound is O(log n) only for sorted case.. Unsorted case tightest O(n) 1 votes 1 votes Satbir commented May 21, 2019 reply Follow Share 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). 0 votes 0 votes Hirak commented May 21, 2019 reply Follow Share 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.. 1 votes 1 votes Hirak commented May 21, 2019 reply Follow Share @Satbir tightest is always calculated based on WORST CASE. 0 votes 0 votes Satbir commented May 21, 2019 reply Follow Share 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. 0 votes 0 votes Hirak commented May 21, 2019 reply Follow Share 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. 2 votes 2 votes Satbir commented May 21, 2019 reply Follow Share yes I agree with you. my mistake. @Hirak 1 votes 1 votes Hirak commented May 21, 2019 reply Follow Share Not a problem, brother.. :) 0 votes 0 votes Satbir commented May 21, 2019 reply Follow Share :) 0 votes 0 votes srestha commented May 21, 2019 reply Follow Share 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 votes 0 votes Satbir commented May 21, 2019 reply Follow Share why will we go for O(n log n) when we can solve it in O(n) ? 0 votes 0 votes srestha commented May 21, 2019 reply Follow Share put Merge Sort for sorting all elements. Then found element in log n time 0 votes 0 votes Satbir commented May 21, 2019 reply Follow Share but O(n) is better than O(n log n) so we should go with O(n) right ? 0 votes 0 votes srestha commented May 21, 2019 reply Follow Share yes, chking every element can do it 0 votes 0 votes Please log in or register to add a comment.
0 votes 0 votes IF it is giving that array is sorted.. Then O(log n) will be correct answer. vikash_thakur answered May 25, 2019 vikash_thakur comment Share Follow See all 0 reply Please log in or register to add a comment.