Input: A positive integer K and a big text. The text can actually be viewed as word sequence. So we don&#39;t have to worry about how to break down it into word sequence.  
Output: The most frequent K words in the text.

My thinking is like this. 

1. use a Hash table to record all words&#39; frequency while traverse the whole word sequence. In this phase, the key is &quot;word&quot; and the value is &quot;word-frequency&quot;. This takes O(n) time. 

2. sort the (word, word-frequency) pair; and the key is &quot;word-frequency&quot;. This takes O(n*lg(n)) time with normal sorting algorithm. 

3. After sorting, we just take the first K words. This takes O(K) time. 

To summarize, the total time is O(n+n*lg(n)+K)， Since K is surely smaller than N, so it is actually O(n*lg(n)).

We can improve this. Actually, we just want top K words. Other words&#39; frequency is not concern for us. So, we can use &quot;partial Heap sorting&quot;. For step 2) and 3), we don&#39;t just do sorting. Instead, we change it to be

2&#39;) build a heap of (word, word-frequency) pair with &quot;word-frequency&quot; as key. It takes O(n) time to build a heap;

3&#39;) extract top K words from the heap. Each extraction is O(lg(n)). So, total time is O(k*lg(n)).

To summarize, this solution cost time O(n+k*lg(n)).

This is just my thought. I haven&#39;t find out way to improve step 1).  
I Hope some Information Retrieval experts can shed more light on this question.

All Word Frequency Solutions on Gang of Coders

Total of 1 Word Frequency Solutions

The Most Efficient Way To Find Top K Frequent Words In A Big Word Sequence