# Codeword constructed by Huffman's algorithm has average length of 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.)

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).