Big O complexities of algorithms - LZW and Huffman

Question

What are the space and time complexities, in Big O notation, for the Lempel-Ziv-Welch and Huffman compression algorithms? Google is failing me.

Thanks,

Francisco

Answer 1

As the dictionary size is fixed and independent of the input length, LZW is in O(n) as each byte is only read once and the complexity of the operation for each character is constant.

And Huffman encoding is also in O(n): First you count the number of occurrences for each input byte, then you sort it and build the output encoding.

Answer 2

Depends on the implementation. They get better all the time. "Huffman" is a bit too common a term. For example, you could mean an explicit tree, an implicit, a dynamic one... But in any case, I guess if you do it very clever you should be able to implement alomost any "Huffman" on O(n), with n being the text-length.

LZW is also implementation-dependent. I do not know off-hand what "O" common implementations have. I guess with big tables you probably have something like O(n log n), but thats just a guess.