algorithms - Word Frequency with Ordering in O(n) Complexity - Computer Science Stack Exchange

algorithms - Word Frequency with Ordering in O(n) Complexity - Computer Science Stack Exchange

1. Read the text and insert all the word encountered into a trie, maintaining in each node a count, how often the word represented by this node has occured. Additionally keep track of the highest word count. -- $O(n)$
2. Initialize an array of size maxWordCount. Entry type are lists of strings. -- $O(n)$, since the count can't be higher.
3. Traverse the trie and for each node add the corresponding string to the array entry indicated by the count. -- $O(n)$, since the total length of strings is bounded by $n$.
4. Traverse the array in descending order and output the desired number of strings. -- $O(n)$, since that is a bound on both the size of and the amount of data in the array.

You can probably replace the trie by other data structures in the first phase.

Read full article from algorithms - Word Frequency with Ordering in O(n) Complexity - Computer Science Stack Exchange