Auxiliary Space of Huffman Coding Algorithm
- Building Huffman Tree: The auxiliary space required to build the Huffman tree is O(N) where N is the number of the unique characters in the input. This space is used to the store the nodes of the tree and the priority queue used for the merging.
- Encoding: During encoding the auxiliary space required is O(1) as it only involves storing the encoded message.
- Decoding: Decoding also requires O(1) auxiliary space as it only involves storing decoded message.
Time and Space Complexity of Huffman Coding Algorithm
Huffman coding is a popular algorithm used for the lossless data compression. It works by assigning variable-length codes to input characters with the shorter codes assigned to more frequent characters. This results in a prefix-free binary code meaning no code is a prefix of the another. The algorithm was developed by the David A. Huffman in 1952 and is widely used in the applications where compression efficiency is critical.
Operation |
Time Complexity |
Space Complexity |
---|---|---|
Building Huffman Tree |
O(N log N) |
O(N) |
Encoding |
O(N) |
O(1) |
Decoding |
O(N) |
O(1) |