# Average codeword length in Huffman encoding at most log n

I am interested in the following question:

Prove that the average length of a codeword constructed by Huffman's algorithm has average length at most $$\log n$$, where $$n$$ is the number of codewords.

I'm thinking of a worst case when the full binary tree (generated by Huffman's algorithm) has height $$n-2$$, but I still have to take the letter frequency into account, and I am stuck.

(Also I observed that the letter frequency shrinks by a factor of two when traversing down the tree.)

Huffman's algorithm is known to be optimal, that is, produce a code which minimizes the average codeword length (with respect to the input distribution).

Let us notice now that there is a code in which each codeword has length $$\lceil \log n \rceil$$, and in particular the average codeword length is $$\lceil \log n \rceil$$ (with respect to any distribution). Hence Huffman's algorithm produces a code in which the average codeword length (with respect to the input distribution) is at most $$\lceil \log n \rceil$$.

Here are two comments. First, we cannot replace $$\lceil \log n \rceil$$ with $$\log n$$. For example, if $$n = 3$$ and you consider the uniform input distribution, then the optimal average codeword length is $$5/3 > \log 3$$.

Second, the average codeword length is only guaranteed to be small with respect to the input distribution. For example, if the input distribution is $$1/2, 1/4, 1/8, \ldots, 1/2^{n-1}, 1/2^{n-1}$$ then the optimal code has codeword lengths $$1,2,3,\ldots,n-1,n-1$$, and so the average codeword length with respect to the uniform distribution is roughly $$n/2$$. The average codeword length with respect to the input distribution, however, is constant (tends to 2).

• The average length of an optimal code is always at most $\lceil\log n\rceil$. – Yuval Filmus Dec 23 '20 at 21:18
• I’m sorry, I don’t understand your question. The average codeword length of an optimal code is always $O(n)$, as well as $O(n!)$, or $O(2^{2^n})$. Big O is just an upper bound. – Yuval Filmus Dec 23 '20 at 21:32
• You can construct prefix codes where the codewords are arbitrarily long. But that’s not so interesting. My example is more subtle, though - the average codeword length is constant. – Yuval Filmus Dec 23 '20 at 21:39
• A bit confused here, your example in last paragraph indicates "average length is at most log(n)" statement is false when input distribution is uniform, because as you mentioned, it is n/2 > log(n) – lennon310 Jan 5 at 16:42
• When the input distribution is uniform and $n = 2^k$, a Huffman code simply consists of all $2^k$ binary strings of length $k$. In particular, the average length is exactly $\log n$. – Yuval Filmus Jan 5 at 16:48