educative.io

Improving time complexity of Top K Frequent Elements

Courses
,
#1

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-top-k-frequent-elements

1 Like
#2

Hello @Isaac_Haseley,

With reference to this query “Improving time complexity on K Closest Points To Origin”.

Indeed, you’re correct, the overall time complexity becomes O(k) + O((n-k) logk).

However, when simplifying the time complexity expression, we distribute the (n - k) term to obtain O(k + n * log k - k * log k). Since k * log k grows way slower than n * log k, especially when n is much larger than k in the worst-case scenario, we can disregard it in the analysis for large n. Therefore, the simplified time complexity is O(n * log k), capturing the most significant term in the function’s growth with increasing input size.

I hope this explanation helps! Feel free to share your opinion on this, thanks!