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


I am having trouble finding a good proof for this statement, I know that determining the number of binomial trees Is determined by using n's binary representation. For example, 13 elements in binary are 1101, 2 ^ {3} + 2 ^ {2} + 2 ^ {0} Therefore 3 binomial trees are necessary, and LN (13) + 1 = 3.56> 3

< P> I just do not know how this proves to be surrounded by logs (n). In general, I struggle with many concepts in the algorithm involving log (n)

Can a clear and brief evidence of this statement? If the required binomial number of trees is given in the binary representation of N by the number 1, then

Then the number of 1 is surrounded by the number of binary numbers, which is the maximum (LG N) + 1 (where LG N Base-2 logarithm, i.e. LG EN = LN (N) / LN (2)). So that O-O bondage has to be given O (log n).


Comments