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.