The disjoint set class - Data Structures and Problem Solving Using Java - page 919

Theorem 24.7

The number of nodes, N ( g ) , in rank group g > 0 is at most N /2 F ( g - 1) .

By Theorem 24.2, there are at most N /2 r nodes of rank r . Summing over the ranks in
group g , we obtain

Proof

Fg ()

∑

N
2 r

N () ≤ ----

r = Fg 1 ( - ) +1

∞
∑

N
2 r

≤ ----

r = Fg 1 ( - )+1

∞
∑

1
2 r

≤ N ----

r = Fg 1 ( - ) +1

∞
∑

N
2 Fg 1

1
2 s

≤ --------------------- ----

( - )+1

s =0

2 N
2 Fg 1

≤

---------------------

( - ) +1

N
2 Fg 1

≤

-----------------

( - )

The maximum number of Canadian pennies deposited in all vertices in rank group g
is at most NF ( g )/2 F ( g - 1) .

Theorem 24.8

Proof

The result follows from a simple multiplication of the quantities obtained in Theorems
24.6 and 24.7.

Theorem 24.9

G ()

F ( g )/2 F ( g - 1) Canadian pennies. The total deposit under rule 2 is at most N Σ g

= 1

Proof

Because rank group 0 contains only elements of rank 0, it cannot contribute to rule 2
charges (it cannot have a parent in the same rank group). The bound is obtained by
summing the other rank groups.