Home > Information Retrieval > Time Complexity of Finding Top k in a set with size n

Time Complexity of Finding Top k in a set with size n

Problem: finding top k in a set with size n
Some people say the time complexity is O(klogn), while others say it is O(n log k). I found a proof from Wikipedia Selection_algorithm entry, which says it should be O(n log k).

C++ also provides the partial_sort algorithm, which solves the problem of selecting the smallest k elements (sorted), with a time complexity of O(n log k).
 

Advertisements
Categories: Information Retrieval Tags:
  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: