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
scroll top