Number of trees in a Fibonacci Heap without CASCADING-CUT

[CGandC]

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.

 

[pbuk]

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

That is not a problem. It may help if you use $N$ to represent the total number of nodes and $T$ the total number of trees. What limit are you summing to with this notation? What does the sum represent?

 

[CGandC]

The sum was supposed to represent the minimal amount of nodes in all trees. Suppose this sum was $S$, after the CONSOLIDATE operation, I'd have at most $O( log(n) )$ trees in the Fibonacci heap.
Now, I think If I were to get an upper-bound of $O(\sqrt{n})$ on the number of trees, I'd need to have about $2^\sqrt{n}$ nodes, because only in such case I'd have $T = log(2^\sqrt{n}) = \sqrt{n}$ trees, so I think the answers lies in this. But on the other hand, the analysis I did does not relate to the sum $S$, so I am perplexed right now..

 

[pbuk]

Please write the sum again as $\sum_{k=1}^X k+1$ (which we know is $\frac{X^2 + 3X}2$). Now write $Y = \sum_{k=1}^X k+1 = \frac{X^2 + 3X}2$. What do you think $X \text{ and } Y$ are here? What is it that is equal to $k + 1$ for each something that has something equal to $k$?

 

[pbuk]

The sum was supposed to represent the minimal amount of nodes in all trees. Suppose this sum was $S$, after the CONSOLIDATE operation, I'd have at most $O( log(n) )$ trees in the Fibonacci heap.

No you wouldn't, you are about to prove that you would have at most $O( \sqrt n )$ trees.

 

[pbuk]

Actually let's start this from scratch: write down an expression for the minimum number of nodes in a tree of depth $k$.

 

[CGandC]

For the trees in the Fibonacci heap, the minimum number of nodes in a tree of order $k$ is $k + 1$. How do I proceed to use this fact together with the fact that after performing CONSOLIDATE operation on all the trees, each tree created in the new heap will be of different order?

 

[pbuk]

If you have $T_0$ trees what is the minimum number of nodes they will cover? What will be the order of these trees? If after consolidation you have the maximum number of trees left, and this number is $T$ write down a list of the orders of the trees.

 

[pbuk]

(actually you were nearly there a few posts ago, I'll try from there)

The sum was supposed to represent the minimal amount of nodes in all trees.

Exactly. So write down an expression for the minimal number $N$ of nodes in $T$ trees (after consolidation).

 

[CGandC]

Like this?:

Let $Tree_1, ... ,Tree_T$ denote the trees after consolidating.
$Tree_1$ will have at-least 1 node ( $Tree_1$ must be of at-least order $0$ )
$Tree_2$ will have at-least 2 node ( $Tree_2$ must be of at-least order $1$ )
.
.
.
$Tree_T$ will have at-least T nodes ( $Tree_T$ must be of at-least order $T-1$ )

the number of their nodes will satisfy $\sum_{k=1}^{T} k \leq n \longrightarrow \frac{T^2}{2} \leq \sum_{k=1}^{T} k = \frac{T(T+1)}{2} \leq n \longrightarrow T^2 \leq 2n \longrightarrow T \leq \sqrt{2}\sqrt{n}$

Edit:
It should be $\sum_{k=1}^{T} k = \frac{T(T+1)}{2} = n$ and from here $\frac{T^2}{2} \leq n$

 

[pbuk]

It should be $\sum_{k=1}^{T} k = \frac{T(T+1)}{2} = n$ and from here $\frac{T^2}{2} \leq n$

Well it's actually $\frac{T^2 + T}{2} \leq n$ but as we are only interested in big-O let's write (with a bit of short-circuiting) $T^2 = \mathcal O (N)$.

So from this, $T = \mathcal O(?)$

 

[CGandC]

$\mathcal O(T) = O(\sqrt{N})$ !
Thanks alot! I was vacillating on this problem for lots of hours, but I feel like I learned a lot about fibonacci heaps.