Q:

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

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?

A:

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)). 

A:

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.

