Basically there are three methods on a Huffman Tree, construction, encoding, and decoding. The time complexity may vary from each other.
We should first notice that (see Wikipedia [link]):
In many cases, time complexity is not very important in the choice of algorithm here, since n here is the number of symbols in the alphabet, which is typically a very small number (compared to the length of the message to be encoded); whereas complexity analysis concerns the behavior when n grows to be very large.
- The complexity of construction is linear (O(n)) if input probabilities are sorted, see this paper. In most cases, we use a greedy O(n*log(n)) construction method: http://www.siggraph.org/education/materials/HyperGraph/video/mpeg/mpegfaq/huffman_tutorial.html
- If you build a bidirection hashtable for all symbols, both encoding and decoding would be constant (O(1)).