Archive for the ‘Information Retrieval’ Category

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

2011-11-02
Leave a comment

Problem: **finding top k in a set with size n**

Some people say the time complexity is O(*k*log*n*), 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

kelements (sorted), with a time complexity of O(nlogk).

Categories: Information Retrieval
topk