In “Top K Elements” it’s been discussed that time complexity to insert an item into the map is O(N*logK), where N is the total number of elements that needs to be inserted and K is the size of the priority queue. In this tutorial it says the time complexity is O(logN), could you please explain on this.
Hi @123tharun
In the lesson of “Top K elements”, it is mentioned that O(NlogK) is the complexity of first to insert ‘K’ numbers in the heap and then iterate through the remaining numbers and at every step, in the worst case, then to extract the minimum number and insert a new number in the heap. It is not mentioned anywhere in the lesson that O(NlogK) is only the complexity to insert elements into the map. So, creating a heap takes O(n) time while inserting into a heap (or priority queue) takes O(log(n)) time.
Hope it will help, Happy Learning 
1 Like
Inserting an element to a priorityqueue when it already had n elements is O(log n).
In this problem, we start with an empty priorityqueue and insert n elements into it.
Is the total time complexity after n elements are inserted = O(log n) or O(n log n)?
I know O(n log n) is the wrong answer because you cant insert n elements when queue already had n elements.
I am just trying to understand how O(log n) is the correct complexity?
The series will look something like this as we insert each element one by one
O(log 0) + O(log 1) + O(log 2) + O(log 3) +…+ O(log n-2) + O(log n-1) + O(log n) = ??
What is the summation of the above series?
where O (log 0) is the complexity to insert the first element because queue is empty therefore n is currently 0.
O(log 1) is the complexity to insert the second element as queue now has 1 element therefore n=1
and so on.