Improving time complexity on K Closest Points To Origin

[Isaac_Haseley]

The solution’s stated time complexity is O(nlogk), because we push/pop n times with a heap of size k.

Instead of pushing the first k elements individually, what if we added them to the heap’s underlying list and then ran heapify? This would take O(k), so our final time complexity would be O(k) + O((n-k)logk) = O((n-k)logk).

---

Course: Grokking Coding Interview Patterns in Python - Learn Interactively
Lesson: https://www.educative.io/courses/grokking-coding-interview-patterns-python/solution-k-closest-points-to-origin

[Dian_Us_Suqlain]

Hello @Isaac_Haseley ,

Thank you for sharing this feedback. After incorporating your suggestion, O(k) is indeed added to the final time complexity, but it is still important to note the relative magnitude of the terms when simplifying the expression. If k is significantly smaller than n, then the constant term O(n) might still be significant compared to O((n - k) * log k). The addition of O(k) does not change the order of growth since O(k) becomes negligible compared to O((n−k) log k).

Therefore, even with the optimization, the overall time complexity, when considering large n, is still effectively described by O(n log k).

I hope this helps! Feel free to share your opinion on this. Thanks!

Happy learning!