Archive for the ‘Information Retrieval’ Category

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).

Categories: Information Retrieval Tags: