Timeline for Heap - Give an $O(n \lg k)$ time algorithm to merge $k$ sorted lists into one sorted list
Current License: CC BY-SA 3.0
3 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Aug 6, 2015 at 14:15 | comment | added | Raphael | @AshwaniGautam That's not tighter at all, since both $O(k)$ and $O(k \log k)$ are dominated. That said, your point is correct; the first initialization of the heap can indeed be done in linear time (in $k$). I guess (hope!) both answerers know that, but it's not crucial here. | |
| Aug 6, 2015 at 13:07 | comment | added | Ashwani Gautam | Actually the tighter time complexity would be O(K+2*NlogK)=O(NlogK). O(K) is tighter bound than O(KlogK), when making a Heap. Refer this for further clarifications. | |
| Jun 24, 2013 at 8:10 | history | answered | Cornelius Brand | CC BY-SA 3.0 |