1 votes 1 votes given an unsorted array with n distinct elements with a property that every element can be atmost k distance from its original position . what is the worst case time complexity to get the sorted array. ans O(n log k) how ..... Algorithms test-series sorting time-complexity + – Chirag arora asked Nov 13, 2017 • retagged Jun 25, 2022 by makhdoom ghaya Chirag arora 1.2k views answer comment Share Follow See 1 comment See all 1 1 comment reply Rishabh Gupta 2 commented Nov 14, 2017 reply Follow Share http://www.geeksforgeeks.org/nearly-sorted-algorithm/ 0 votes 0 votes Please log in or register to add a comment.
1 votes 1 votes 1.using heap sort..take first k+1 element and make min heap O(k)...and delete min....and take one element from remaining n-k and insert in to heap-O((n-k)logk) again delete min...and so on... hs_yadav answered Nov 13, 2017 hs_yadav comment Share Follow See 1 comment See all 1 1 comment reply jaig commented Jan 8, 2018 reply Follow Share why are we adding just one element? "atmost k distance" means it can be on the either not just one. 1 votes 1 votes Please log in or register to add a comment.
