- #1

CGandC

- 326

- 34

- Homework Statement
- The question relates to Fibonacci heaps. Suppose DECRASE-KEY was implemented without CASCADING-CUT.

Prove that after CONSOLIDATE operation on the Fibonacci heap, the amount of trees in the heap is at most ## O( \sqrt{n} ) ##.

- Relevant Equations
- ( The question is in the context of the section about Fibonacci heaps from 2nd edition of CLRS )

--- ##n## refers to the amount of nodes in the Fibonacci heap.

--- order of a tree in heaps is defined as the number of children of a root.

--- In a different exercise I showed that the minimal amount of nodes in a tree ( from Fibonacci heap in which DECREASE-KEY is implemented without CASCADING-CUT ) of order ##k## is ##k+1##.

I know that the maximum number of trees in a heap will be when all the trees are of smallest order as possible. Then, after performing CONSOLIDATE operation on the heap, all the newly created trees in the heap will be of different orders. Since in a different exercise I showed that the minimal amount of nodes in a tree ( from Fibonacci heap in which DECREASE-KEY is implemented without CASCADING-CUT ) of order ##k## is ##k+1##, thus, we can sum the nodes from all the minimal trees, bound them by ##n## and get an upper-bound of ## O( \sqrt{n} ) ## for the number of trees.

The above attempt is not necessarily correct and has logical gaps. My main trouble is that the sum ## \sum_{k=1}^{k=n} k+1 ## will give me an upper bound of ##O(n^2)## and not of ##O(\sqrt{n})##. In any-case I'm stuck and I'd really appreciate help, I have no idea how to proceed and I feel like I've been brooding for too-long on this problem.

The above attempt is not necessarily correct and has logical gaps. My main trouble is that the sum ## \sum_{k=1}^{k=n} k+1 ## will give me an upper bound of ##O(n^2)## and not of ##O(\sqrt{n})##. In any-case I'm stuck and I'd really appreciate help, I have no idea how to proceed and I feel like I've been brooding for too-long on this problem.