educative.io

Does it take O(k) time to add k items into the heap?

Courses
,
#1

The first sentence in the Time Complexity paragraph states, “The first loop inserts k elements into an array, which takes O(k) time complexity.” Wouldn’t that be O(k log k) since we are adding items to the binary heap?

The last sentence reports, “The overall time complexity is therefore O(k + (n − k) × log k), which simplifies to O((n − k) × log k).” If we are running O(k log k) in the first loop, wouldn’t that be a total of O(n log k) in the worst case?

Course: Grokking Coding Interview Patterns in JavaScript - Learn Interactively
Lesson: Solution: Kth Largest Element in an Array - Grokking Coding Interview Patterns in JavaScript

Course: Grokking Coding Interview Patterns in JavaScript - Learn Interactively
Lesson: Solution: Kth Largest Element in an Array - Grokking Coding Interview Patterns in JavaScript

#2

Hello @Elvin_Kosova,

Thank you for your feedback. You are right, the time complexity for adding items in the heap is O(k log(k)) instead of O(k) in the first pass. In the second pass, it takes O((n - k) * log(k)) time to add and delete elements from the heap.

Overall, the time complexity will be O(n * log(k)). This has been fixed in the lesson, and we’ll let you know once the updated version is live.

If you have any more questions or need further clarification, please let us know.

Happy learning!

1 Like