Average codeword length in a Huffman tree is $\Omega(\log n)$
-
05-11-2019 - |
Question
Prove that the average codeword length in a Huffman tree is $\Omega(\log n)$, where $n$ is the number of characters.
My try:
I think that the worst case is when the tree is full and all the characters are in the highest level.
Therefore: $n=2^h \to h=\log n$, and the average codeword length is $\Omega(\log n)$.
Am I missing something?
No correct solution
Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange