The obvious algorithm is to sort all the words in order of increasing frequency, then print the 100 first. This algorithm is O(n log n) because of the sorting. It generates the list in order of frequency.
There is an O(n) algorithm that first picks some random item as pivot, then does a partioning like QuickSort where items with higher frequency than the pivot are moved to the front of the array and those with lower frequency to the back.
If the first partition has more than a 100 items, then the algorithm only has to recurse into that part. If it has fewer (k), then it prints everything in the first partition, and recurses into the second to generate the 100 - k best items.
This is expected O(n) and will not generate the list in order of frequency.
The obvious algorithm is to sort all the words in order of increasing frequency, then print the 100 first. This algorithm is O(n log n) because of the sorting. It generates the list in order of frequency.
There is an O(n) algorithm that first picks some random item as pivot, then does a partioning like QuickSort where items with higher frequency than the pivot are moved to the front of the array and those with lower frequency to the back.
If the first partition has more than a 100 items, then the algorithm only has to recurse into that part. If it has fewer (k), then it prints everything in the first partition, and recurses into the second to generate the 100 - k best items.
This is expected O(n) and will not generate the list in order of frequency.