What is the running time and space complexity of a huffman decode algorithm?

Question

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?

Answer 1

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.

1. 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
2. If you build a bidirection hashtable for all symbols, both encoding and decoding would be constant (O(1)).

Answer 2

Assume an encoded text string of length n and an alphabet of k symbols.

For every encoded symbol you have to traverse the tree in order to decode that symbol. The tree contains k nodes and, on average, it takes O(log k) node visits to decode a symbol. So the time complexity would be O(n log k).

Space complexity is O(k) for the tree and O(n) for the decoded text.