I’m reading Algotithms by Jeff Erickson, and I have trouble in solving the exercise in Greedy Algorithms:

(b) Suppose the total length N of the unencoded message is bounded by a
polynomial in the alphabet size n . Prove that the any Human tree for
the frequencies f[1…n] has depth O(log n).

I don’t know how to prove this, because I think the depth could reach n-1, like this: f[1…n] = {1, 1, 1, 3, 4, 7, 11, 18, 29, …} (the Lucas number).

Could you please help me? Thanks!