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,

A string with different characters, say “ACCEBFFFFAAXXBLKE”
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?

  • $\begingroup$ What is the Huffman coding problem? $\endgroup$ Apr 29, 2021 at 10:05
  • $\begingroup$ @YuvalFilmus It's Huffman encoding $\endgroup$
    – t24akeru
    Apr 29, 2021 at 10:23
  • $\begingroup$ What is the input, and what is the desired output? $\endgroup$ Apr 29, 2021 at 10:24
  • $\begingroup$ @YuvalFilmus input: a string with different characters, like “ACCEBFFFFAAXXBLKE”, output: Huffman code $\endgroup$
    – t24akeru
    Apr 29, 2021 at 10:27
  • 1
    $\begingroup$ How is the output presented? Also, instead of answering in the comments, please update your question. Don't add an "UPDATE:" section; instead, just insert the details where appropriate. $\endgroup$ Apr 29, 2021 at 10:37


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.