Java Reference
In-Depth Information
Thus we have the deposits under rules 1 and 2. The total is
GN
()
∑
()
2
Fg
1
Fg
MGN
(
()
+
2
)
+
N
----------------
(24.1)
(
-
)
g
=
1
We still have not specified
G
(
N
) or its inverse
F
(
N
). Obviously, we are free to
choose virtually anything we want, but choosing
G
(
N
) to minimize the bound
in Equation 24.1 makes sense. However, if
G
(
N
) is too small,
F
(
N
) will be
large, thus hurting the bound. An apparently good choice is
F
(
i
) to be the
function recursively defined by
F
(0) and
F
(
i
) = 2
F
(
i
- 1)
, which gives
G
(
N
) =
1+
⎣
log*
N
⎦
. Figure 24.23 shows how this choice partitions the ranks. Note
that group 0 contains only rank 0, which we required in the proof of Theorem
24.9. Note also that
F
is very similar to the single-variable Ackermann's func-
tion, differing only in the definition of the base case. With this choice of
F
and
G,
we can complete the analysis in Theorem 24.10.
Now we can spec-
ify the rank groups
to minimize the
bound. Our choice
is not quite minimal,
but it is close.
Theorem 24.10
The running time of the union/find algorithm with
M
= Ω(
N
)
find
operations is
O
(
M
log*
N
)
.
Proof
Insert the definitions of
F
and
G
in Equation 24.1. The total number of U.S. pennies is
O
(
MG
(
N
)) =
O
(
M
log*
N
)
. Because
F
(g) = 2
F
(
g
- 1)
, the total number of Canadian pen-
nies is
NG
(
N
) =
O
(
N
log*
N
)
, and because
M
=
(
N
)
, the bound follows.
Ω
figure 24.23
Actual partitioning of
ranks into groups
used in the proof
Group
Rank
0
0
1
1
2
2
3
3, 4
4
5 through 6
5
17 through 65,536
65,537 through 2
65,536
6
7
Truly huge ranks
Search WWH ::
Custom Search