CODEWITHSUNDEEP
algorithmsorting
troose56
troose56

Reputation: 11

What has a time complexity of O(nlogk)

To sort a basic array of integers of size n find the k smallest elements, what function would cause a time complexity of O(nlogk)?

When looking at a merge sort for example, it gives has the time complexity of O(nlogn). Where does k come into the time complexity?

Upvotes: 1

Views: 1253

Answers (1)

kaya3
kaya3

Reputation: 51063

Put the numbers into a priority queue one-by-one. Every time you insert a number, if the queue now has more than k elements, then remove the largest one. Finally, poll the elements remaining in the queue to get the k smallest from the original array, in reverse order.

This runs in O(n log k) time assuming your priority queue of size at most k+1 can insert and find-and-remove-max in O(log k) time. A heap or balanced BST will work.

Upvotes: 2

Related Questions