Databases Reference
In-Depth Information
We can indicate the occurrence of any particular event, as shown in Figure
2.2
.Inthis
case, we have a sequence of three selections. Each selection is between two equally likely
possibilities. Therefore,
H
1
1
8
,...,
1
8
8
,
=
A
(
8
)
H
1
H
1
2
H
1
1
2
1
2
1
2
1
1
2
=
2
,
+
2
,
+
2
,
2
H
1
1
1
2
+
2
,
(5)
H
1
2
H
1
1
2
1
2
1
1
2
+
2
,
+
2
,
2
H
1
1
1
2
+
2
,
3
H
1
1
2
=
2
,
=
3
A
(
2
).
In other words,
)
(The rather odd way of writing the right-hand side of Equation (
5
)istoshowhowtheterms
correspond to the branches of the tree shown in Figure
2.2
.) We can generalize this for the
case of
n
A
(
8
)
=
3
A
(
2
k
m
as
=
k
m
A
(
n
)
=
A
(
)
=
mA
(
k
)
Similarly, for
j
l
choices,
j
l
)
We can pick
l
arbitrarily large (more on this later) and then choose
m
so that
k
m
A
(
)
=
lA
(
j
j
l
k
(
m
+
1
)
Taking logarithms of all terms, we get
m
log
k
l
log
j
(
m
+
1
)
log
k
Now divide through by
l
log
k
to get
m
l
1
l
Recall that we picked
l
arbitrarily large. If
l
is arbitrarily large, then
l
log
j
log
k
m
l
+
is arbitrarily small. This
log
j
log
k
can be made arbitrarily close to
l
means that the upper and lower bounds of
by picking
l
arbitrarily large. Another way of saying this is
<
m
l
−
log
j
log
k
where
can be made arbitrarily small. We will use this fact to find an expression for
A
(
n
)
and
1
1
hence for
H
(
n
,...,
n
)
.
