Information Technology Reference
In-Depth Information
parent vertex
.The
length of a path
in a tree is the number of edges on that path. The
left (right) subtree
of a vertex is the subtree that is detached by removing the left (right)
descending edge. A
binary search tree
is a binary tree that has one key at each vertex. (This
definition assumes that all the keys in the tree are distinct.) The value of this one key is larger
than that of all keys in the left subtree, if any, and smaller than all keys in the right subtree, if
any. A
balanced binary search tree
is a binary search tree in which all paths have length
k
or
k
+
1 for some integer
k
.
LEMMA
11.9.1
The length of the longest path in a binary tree with
n
vertices is at least
log
2
(
n
+
1
)
/
2
.
Proof
A longest path in a binary tree with
n
vertices is smallest when all levels in the tree
are full except possibly for the bottom level. If such a tree has a longest path of length
l
,it
has between 2
l
and 2
l
+
1
−
1 vertices. It follows that the longest path in a binary search tree
containing
n
keys is at least
log
2
(
n
+
1
)
/
2
.
The
binary search procedure
searches a binary search tree for a key value
v
.Itcompares
v
against the root value, stopping if they are equal. If they are not equal and
v
is less than the
key at the root, the search resumes at the root vertex of the left subtree. Otherwise, it resumes
at the root of the right subtree. The procedure also stops when a leaf vertex is reached.
We can now state bounds on the cost on the HMM for the logarithmic cost function
ν
(
a
)=
. This function applies when the memory hierarchy is organized as a binary
tree in which the low-indexed memory locations are located closest to the roots and the time
to retrieve an item is proportional to the number of edges between it and the root. We use it
to illustrate the techniques developed in the previous section.
Theorem
11.9.1
states lower performance bounds for straight-line algorithms. Thus, the
computation time is independent of the particular argument of the function
f
provided as
input. Matching upper bounds are derived in the following section. (The logarithmic cost
function is polynomially bounded.)
log
2
a
THEOREM
11.9.1
The cost function
ν
(
a
)=
log
2
a
on the HMM for the
n × n
matrix
multiplication function
f
(
n
)
A×B
realized by the classical algorithm, the
n
-point FFT associated with
the graph
F
(
d
)
,
n
=
2
d
, comparison-based sorting on
n
keys
f
(
n
)
sort
, and binary search on
n
keys,
f
(
n
)
BS
, satisfies the following lower bounds:
K
ν
(
f
(
n
)
A×B
)=Ω(
n
3
)
Matrix multiplication:
K
ν
(
F
(
d
)
)=Ω(
n
log
n
log log
n
)
Fast Fourier transform:
K
ν
(
f
(
n
)
Comparison-based sorting:
sort
)=Ω(
n
log
n
log log
n
)
K
ν
(
f
(
n
)
BS
)=Ω(log
2
n
)
Binary search:
Proof
The lower bounds for the logarithmic cost function
ν
(
a
)=
log
2
a
use the fact
that
Δ
ν
(
a
)=
1when
a
=
2
k
for some integer
k
but is otherwise 0. It follows from (
11.5
)
Search WWH ::
Custom Search