2

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?

Brian
  • 7,098
  • 15
  • 56
  • 73
  • 1
    This question appears to be off-topic because it is not about computer a programming problem and belongs on http://cs.stackexchange.com/ – Ted Hopp Feb 18 '14 at 15:45
  • do you mean height of heap ? – Aseem Goyal Feb 18 '14 at 15:52
  • @anon No, I mean the number of binomial trees that must be joined together as left most child of preceding binomial tree to construct a binomial heap that contains n elements – Brian Feb 18 '14 at 17:40

1 Answers1

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

user2566092
  • 4,631
  • 15
  • 20