1 votes 1 votes For searching an element from heap,then delete it from heap Why will it take O(n+log n) time and not O(n log n) time? DS data-structures binary-heap time-complexity + – srestha asked Dec 8, 2017 • recategorized Jul 7, 2022 by Lakshman Bhaiya srestha 513 views answer comment Share Follow See all 0 reply Please log in or register to add a comment.
1 votes 1 votes you just need to search it first, O(n) & then delete(swap it with last element and call heapify which will take log(n). T(n) = O(n + log(n)) vishalshrm539 answered Dec 8, 2017 vishalshrm539 comment Share Follow See all 6 Comments See all 6 6 Comments reply srestha commented Dec 8, 2017 reply Follow Share but why not nlogn? I mean + means OR but here both n and logn required. So, why not nlogn ? 0 votes 0 votes Anu007 commented Dec 8, 2017 reply Follow Share For searching an element from heap,then delete it from heap searching take O(n) in heap and deletion take O(logn) right for single element. O(n+logn)= O(n) search one for loop one function + heapify another function inside main 1 votes 1 votes vishalshrm539 commented Dec 9, 2017 reply Follow Share we are searching and deleting only a single element Read question an element. and + means addition here, it is not RE. 1 votes 1 votes Diksha Aswal commented Dec 9, 2017 reply Follow Share deleting n elements will take O(nlogn) ? 1 votes 1 votes saxena0612 commented Dec 9, 2017 reply Follow Share Deleting $n$ elements will take $n \ * \ O(n+logn) \ = O(n^{2})$ 3 votes 3 votes Diksha Aswal commented Dec 9, 2017 reply Follow Share oh yes, thanks 0 votes 0 votes Please log in or register to add a comment.