Can you get O(n) with a word frequency algorithm?

By a word frequency algorithm: An algorithm gets a document as an input, and returns each unique word along with the number of times it has appeared in the document.

For example:

in:"Hello my name is Hello" out: {'Hello':2, 'is':1, 'my':1, 'name':1}

In my implementation, I used a hash table to store the words.

But I've seen uses of a trie, but I don't understand why this improves runtime.

I've read that you can get O(n). I assume with a trie correct?

• N is the size of your input document. But if you assume that the document, no matter the length, selects words from a constant-sized dictionary, then word frequency is O(N) and the data structure doesn't make much difference because the output size is O(1). Now, if you're comparing actual implementations, trie might or might not be faster than a hash – depends on the constants. – chrisleague Jul 11 '15 at 0:46
• 1. Do you care about theoretical worst-case running time, or practical performance? 2. Is this English (where words have a small fixed upper bound on their length, e.g., no word has more than 100 letters), or is it arbitrary text? – D.W. Jul 11 '15 at 2:14
• @chrisleague I think the question is asking for an algorithm with running time $O(n)$ where, as you say, $n$ is the length of the document. Yes, each word will appear with frequency $O(n)$ but I don't think that's what's being asked about. But the output isn't $O(1)$: it's a list of all the words and their frequencies, which could, in the worst case, be slightly longer than the original document (consider the case where each word occurs exactly once). – David Richerby Jul 11 '15 at 4:38
• @D.W. I'd like to know both. It's English. – Tai Jul 11 '15 at 5:34

If the size of the alphabet is constant and $n$ denotes the length of the document (i.e. the total number of characters), you can indeed use Tries to get $O(n)$ running time - regardless of the length of the words.

In a Trie, you can search for (or insert) a word in time linear in the length of the word. You can use a Trie to keep track of the words as you encounter them in the text, and in each Trie node corresponding to a word you can store that word's frequency (which is updated each time you encounter it).

The running time of this algorithm is indeed $O(n)$: the sum of all the lengths of the words in the documents is precisely the length of the document. Note that you can also traverse the Trie (and list the words it contains to generate the desired output) in $O(n)$ (since the number of nodes in the Trie is at most $n$).

There is a lower bound of $\Omega(n\log n)$ in the comparison model for ELEMENT DISTINCTNESS, which is the following problem: given $n$ elements, decide whether they are all different. Your task can be used to solve ELEMENT DISTINCTNESS, so in the comparison model (if you are only allowed to compare elements) there is no $O(n)$ algorithm.

Using a hash table, you can indeed guarantee a running time of $O(n)$ on average. That doesn't contradict the lower bound since you are taking hashes of strings, which is not allowed in the comparison model.

• There seems to be a slight catch: is $n$ the number of words, or the total length of the text? – Hendrik Jan Jul 11 '15 at 8:44
• @HendrikJan Here $n$ is the number of words. If all the words have the same length $\ell$ (up to a constant), then each comparison takes $\Theta(\ell)$ in the worst case, so we get a lower bound in terms of total length. – Yuval Filmus Jul 11 '15 at 14:55
• You need to read log n bits to distinguish n unique values. – KWillets Jul 11 '15 at 15:15