What is the running time and space complexity of a huffman decode algorithm?
algorithm, big-o, huffman-code
Solution
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)).
Problem
Say we started with a text file like: ``` a 00 b 01 c 10 d 11 00000001011011 ``` The algorithm would be the typical one where you use the prefixes to build a Huffman tree, read in the encoded bits while traversing the tree until you reach a leaf, then returning the character in at that leaf. Could someone explain how I would determine the running time and space complexity?