2 votes 2 votes Can anyone please explain how to find “ i “ smallest elements from an array whose elements are distinct Please use max heap to explain the working input : n distinct elements output : i smallest elements DS algorithms binary-heap data-structures + – Thor-o-s asked Sep 1, 2022 Thor-o-s 391 views answer comment Share Follow See all 0 reply Please log in or register to add a comment.
Best answer 5 votes 5 votes Using max heap we can find i smallest elements in O( n * log i ) time this method is very popular in coding interviews [ Jiren ] answered Sep 1, 2022 selected Sep 2, 2022 by Thor-o-s [ Jiren ] comment Share Follow See all 4 Comments See all 4 4 Comments reply Thor-o-s commented Sep 2, 2022 reply Follow Share @[ Jiren ] Nice answer thank you ;) 0 votes 0 votes KartikGawande commented Sep 3, 2022 reply Follow Share We have taken 'i' to be constant right? That's why we r going from O((n-i) logi + i) to O(n(logi)).. Right? 0 votes 0 votes [ Jiren ] commented Sep 3, 2022 reply Follow Share @KartikGawande NO Even if i depends on “n” like i = n the time complexity still wont exceed n*logi because (n-n)*logi+n = n which is O(nlogn) Also remember that we cant take any parameter as constant unless mentioned in Algorithms and Data Structures But writing Θ( n*logi ) is wrong we should write Θ( (n-i) logi + i ) 2 votes 2 votes KartikGawande commented Sep 4, 2022 reply Follow Share @[ Jiren ] i see 0 votes 0 votes Please log in or register to add a comment.