Prove the number of binomial trees in a binomial heap with n elements is at most O(log n)

Question

I am having trouble locating a good proof for this statement. I know how to determine the number of binomial trees is determined by using the binary representation of n. For example, 13 elements is 1101 in binary, 2^{3}+2^{2}+2^{0} So 3 binomial trees are required, and ln(13) + 1 = 3.56 > 3

I just do not know how to prove its bounded by log(n). In general, I struggle with many concepts in algorithm involving log(n)

Can someone provide a clean and concise proof of this statement?

Answer 1

If the number of binomial trees required is given by the number of 1's in the binary representation of n, then the number of 1's is bounded by the number of binary digits, which is at most (lg n) + 1 (where lg n is base-2 logarithm, i.e. lg n = ln(n) / ln(2)). So that would give the big-O bound of O(log n).