0
$\begingroup$

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?

Improve this question
$\endgroup$
12
  • $\begingroup$ What is the Huffman coding problem? $\endgroup$
    – Yuval Filmus
    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$
    – Yuval Filmus
    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$
    – Yuval Filmus
    Apr 29, 2021 at 10:37

0

Reset to default

Your Answer

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