1 votes 1 votes Given a set of n distinct numbers, determine the smallest four numbers in this set using comparisons? How much comparisons will be needed? My Answer is -> (n-1)+O(lgn) Algorithms algorithms time-complexity + – iarnav asked Apr 1, 2018 edited Apr 1, 2018 by iarnav iarnav 432 views answer comment Share Follow See all 5 Comments See all 5 5 Comments reply Show 2 previous comments Tesla! commented Apr 1, 2018 reply Follow Share how explain me approach please 0 votes 0 votes Sambit Kumar commented Apr 1, 2018 reply Follow Share same question https://www.gateoverflow.in/27194/tifr2014-b-9 0 votes 0 votes iarnav commented Apr 1, 2018 reply Follow Share Explained below by Abhishek! :) 0 votes 0 votes Please log in or register to add a comment.
Best answer 1 votes 1 votes total comparisions =(n-1)+O(lgn). abhishekmehta4u answered Apr 1, 2018 selected Apr 1, 2018 by iarnav abhishekmehta4u comment Share Follow See all 3 Comments See all 3 3 Comments reply iarnav commented Apr 1, 2018 reply Follow Share @abhishekmehta4u Thanks, man! :) 1 votes 1 votes Tesla! commented Apr 1, 2018 reply Follow Share First minimum n-1 comparison not 0 1 votes 1 votes iarnav commented Apr 3, 2018 reply Follow Share Right on, brother! 0 votes 0 votes Please log in or register to add a comment.
2 votes 2 votes using min heap construct min heap using build heap -------->o(n). delete root node you will get first smallest ......>o(logn). again delete root node you will get second min ------->o(logn) again delete root node you will get third min ------->o(logn) again delete root node you will get forth min ------->o(logn) total comparisions =n+o(logn) abhishekmehta4u answered Apr 1, 2018 edited Apr 1, 2018 by abhishekmehta4u abhishekmehta4u comment Share Follow See all 0 reply Please log in or register to add a comment.