# How to prove that the lower bound of the Huffman coding problem is $\Omega(n \log n)$?

how to prove that the lower bound of the Huffman coding problem is $$\Omega(n \log n)$$?

Here Huffman coding problem is Huffman encoding.

For example,

Input:
A string with different characters, say “ACCEBFFFFAAXXBLKE”
Output:
Code for different characters:
Data: K, Frequency: 1, Code: 0000
Data: L, Frequency: 1, Code: 0001
Data: E, Frequency: 2, Code: 001
Data: F, Frequency: 4, Code: 01
Data: B, Frequency: 2, Code: 100
Data: C, Frequency: 2, Code: 101
Data: X, Frequency: 2, Code: 110
Data: A, Frequency: 3, Code: 111


I already saw that we can know that the bound of the sorting problem is $$\Omega(n \log n)$$ by using decision tree.

the number of leaves: $$n!$$
(the number of leaves in a half tree with a height of $$h) \leq 2^h$$
$$\Rightarrow n! \leq 2^h \Rightarrow h \geq \log n!$$

$$\Rightarrow \log n! \fallingdotseq n \log n - n = \Omega(n \log n)$$

So I thought I could also use the decision tree to get the lower bound of the Huffman coding problem but I am not sure how to construct the decision tree for Huffman coding problem, like how many leaves are needed,...

Please tell me how to construct the decision tree or is my attempt to tackle this proof wrong?

• What is the Huffman coding problem? – Yuval Filmus Apr 29 at 10:05
• @YuvalFilmus It's Huffman encoding – t24akeru Apr 29 at 10:23
• What is the input, and what is the desired output? – Yuval Filmus Apr 29 at 10:24
• @YuvalFilmus input: a string with different characters, like “ACCEBFFFFAAXXBLKE”, output: Huffman code – t24akeru Apr 29 at 10:27