Information Technology Reference
In-Depth Information
comparisons. A binary tree with
N
leaves has a longest path of length at least
log
2
N
because
if it were smaller, it would have fewer than 2
log
2
N
<N
leaves. Since the length of the longest
log
2
N
path is an integer, it must be at least
. We summarize this result as a lemma that uses
the lower bound on
n
!
giveninProblem
2.23
.
LEMMA
11.8.1
The length of the longest path in a binary decision tree that sorts
n
inputs is at
least
log
2
n
!
=Θ(
n
log
n
)
.
The
multiway decision tree
in Fig.
11.15
extends the above concept by permitting multi-
ple comparisons at each vertex. 2
k
outcomes are possible if
k
comparisons of variable pairs are
associated with each vertex.
THEOREM
11.8.1
Let
B
divide
M
and
M
divide
n
. Under Assumption
11.8.1
on the BTM,
in the worst case the number of block I/O steps to sort a set of
n
records using
M
words of primary
memory and block size
B
,
T
BTMsort
(
n
)
, satisfies the following bounds for
B
≤
M/
2
and
M
large:
T
BTMsort
(
n
)=Θ
max
n
B
,
(
n/B
)log(
n/B
)
log(
M/B
)
Proof
Let's now apply the multiway decision tree to the BTM. Since each path in such a tree
corresponds to a sequence of comparisons by the CPU, the tree must have at least
n
!
leaves.
To complete the lower-bound derivation we need to determine the number of descendants
of vertices in the multiway tree.
Initially the
n
unsorted words are stored in
n/B
blocks in the secondary memory. The
first time one of these blocks is moved to the primary memory, up to
B
!
permutations
can be performed on the words in it. No more permutations are possible between these
words no matter how many times they are simultaneously in primary memory, even if they
return to the memory as members of different blocks. When a block of
B
words arrives in
the
M
-word memory, the number of possible permutations between them (given that the
order among the
M
−
B
words originally in the memory has previously been taken into
x
2
:
x
3
x
3
:
x
5
2
≤
3
2
≤
3
2
>
3
2
>
3
≤
≤
3
5
3
>
5
3
5
3
>
5
x
3
:
x
4
x
2
:
x
4
x
2
:
x
4
x
2
:
x
5
x
1
:
x
3
x
3
:
x
4
x
1
:
x
3
x
1
:
x
5
Figure 11.15
A multiway decision tree in which multiple comparisons of keys are made at each
vertex.
Search WWH ::
Custom Search