Average codeword length in Huffman encoding at most log n
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 &gt; \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).