2 votes 2 votes Algorithms algorithms time-complexity test-series + – thepeeyoosh asked Jan 11, 2018 retagged Jul 17, 2022 by makhdoom ghaya thepeeyoosh 1.0k views answer comment Share Follow See all 6 Comments See all 6 6 Comments reply Mk Utkarsh commented Jan 11, 2018 reply Follow Share the set K will be constant for a given instance hence we just need to build a min heap or max heap which takes O(n) time and accessing Kth smallest elements will take constant time. hence c) O(n) 0 votes 0 votes thepeeyoosh commented Jan 11, 2018 reply Follow Share No bro it's wrong, here k is not constant they only given instant for problem understanding. Here we can use two approaches which is using min heap and selection procedure technique. By using this ans is coming from my side O(nr) but ans was given O(n logr) 1 votes 1 votes Mk Utkarsh commented Jan 11, 2018 reply Follow Share yes i thought so if r is varies then O(n*r) that's what i thought but somehow got convinced because of this https://gateoverflow.in/130879/algorithm-test-2-24 but yeah you are right r varies according to n and it should be O(n.r) but which is not the correct one :/ 1 votes 1 votes thepeeyoosh commented Jan 11, 2018 reply Follow Share this link doesn't open any question. please check the link. 0 votes 0 votes Mk Utkarsh commented Jan 11, 2018 reply Follow Share ohh that's because one has to attempt that test to access the question :| 0 votes 0 votes Nakul Bhardwaj commented Jul 10, 2018 reply Follow Share Build heap : O(n) Ex :To find 2nd minimum Delete root 2 times - 2*log(n) To find rth minimum - r*log(n) Total complexity: O(n + r*log(n)) = O(n) (since r<n and some constant therefore n is asymptotically larger than r*log(n) ) 0 votes 0 votes Please log in or register to add a comment.
0 votes 0 votes the ans is o(nlogr) because .... first we build a heap and then one by one we get logr times required to call and balance it adi037raj answered Dec 5, 2018 adi037raj comment Share Follow See all 0 reply Please log in or register to add a comment.