2 votes 2 votes Algorithms algorithms time-complexity made-easy-test-series + – rahul sharma 5 asked Oct 18, 2017 • retagged Jul 17, 2022 by makhdoom ghaya rahul sharma 5 931 views answer comment Share Follow See all 12 Comments See all 12 12 Comments reply rahul sharma 5 commented Oct 18, 2017 reply Follow Share I can sort both and then nuts[i] matches with bolts[i]. 2*nlogn. Is this correct? 1 votes 1 votes VS commented Oct 18, 2017 reply Follow Share Correct. . Implementation of quick sort 1 votes 1 votes joshi_nitish commented Oct 18, 2017 reply Follow Share you can not sort nuts and bolts, nuts can not be compared with other nuts, same for bolts.. 1 votes 1 votes rahul sharma 5 commented Oct 19, 2017 reply Follow Share Got it @joshi,I didnt read it carefully. I have seen some solutions based on quick sort,but quick sort can give n^2 in worst case.But the answer given is nlogn.Can you please help here? 0 votes 0 votes junaid ahmad commented Oct 19, 2017 reply Follow Share @rahul sharma 5 why it is coming o(nlogn) because once you sort the nut according to bolt by comparing sizes,once you do this half of them is in left and half of them is in right. 0 votes 0 votes joshi_nitish commented Oct 19, 2017 reply Follow Share @rahul sharma 5 it think they have taken average case of O(nlogn).. 0 votes 0 votes joshi_nitish commented Oct 19, 2017 reply Follow Share @junaid ahmad this is not true, though in avg case what you have said is correct, but in worst case, the all the rest bolts(except matching bolt) can go to right of matched bolt or all of them can go to left of matched bolt leading to worst case scenario,giving time complexity of O(n2) 0 votes 0 votes junaid ahmad commented Oct 19, 2017 reply Follow Share @ joshi_nitish so what should we mark here? In question it is also mentioned that if we do this procedure effectively I think that is why they have considered avg casesl.whta you think ? 0 votes 0 votes joshi_nitish commented Oct 19, 2017 reply Follow Share @junaid ahmad , on average i think O(nlogn) should be correct 0 votes 0 votes Tesla! commented Oct 21, 2017 reply Follow Share http://www.geeksforgeeks.org/nuts-bolts-problem-lock-key-problem/ best solution possible 0 votes 0 votes rahul sharma 5 commented Oct 21, 2017 reply Follow Share But worst case should be 0(n^2)? @joshi_nitish,question does not says average case here? 0 votes 0 votes joshi_nitish commented Oct 21, 2017 reply Follow Share yes it should be O(n^2) in worst case.. 1 votes 1 votes Please log in or register to add a comment.
0 votes 0 votes This is a classical algo problem How intruiging this prblem is makes you fall in love with algorithms It may seem at a glance that it is nlogn but the truth is it isnt It is O(n^2) https://courses.engr.illinois.edu/cs473/sp2017/notes/02-nutsbolts.pdf shashankrustagi answered Dec 31, 2020 shashankrustagi comment Share Follow See all 0 reply Please log in or register to add a comment.