In fact, we can achieve it by any using any height balanced tree and do an in-order traversal for K elements. Again, it takes O(n log n).
Also, I think even using heap tree, time complexity will be O(n log n) not O(n log k). Its because, we need to scan the entire list and insert into heap and adjust. This takes O(n log n) -- right??
3 comments:
In fact, we can achieve it by any using any height balanced tree and do an in-order traversal for K elements. Again, it takes O(n log n).
Also, I think even using heap tree, time complexity will be O(n log n) not O(n log k). Its because, we need to scan the entire list and insert into heap and adjust. This takes O(n log n) -- right??
It would be O(n log k) because we should maintain a heap of size k.
Inserting an element into this heap will be O(log k).
This has to be done (worse case) for n elements. so O(n log k).
Yeah, Got it. Thanks!
Post a Comment