3 ms·
In O(log n), what is n? The number of characters? I would've thought that was O(n log n) (due to the sort).
by dbaupp 12y ago
In O(log n), what is n? The number of characters? I would've thought that was O(n log n) (due to the sort).
- emillon 12y agon is the number of words in the dictionary.
- binarymax 12y agoYes good point, allow me to clarify. n is the number of keys in the dictionary (log n for the binary search). I suppose yes it is probably the more complex O(n log n) to sort the letters before the search.
- bradleyjg 12y agoIf n is the number of keys in the dictionary, then the whole procedure would not be O(n log n), it'd be O(m log n) where m is the number of letters. Given that n >> m, I would think your original statement is correct.
- dbaupp 12y agoOh, so I guess it is strictly O(m log m + log n) if m is the number of letters. You can theoretically get it to be O(m log m) using a hashmap (makes lookups O(1)) or trie (lookups are O(m)).