Information Technology Reference
In-Depth Information
K
U
m
(
f
)
of computing
f
is
directly related to the number of I/O operations with the red-blue pebble game played with
S
=
m
red pebbles discussed in Sections
11.5.2
and
11.5.3
. For this reason we call this cost
I/O complexity
. The principal difference is that in the HMM no cost is assessed for data
stored in the first
m
memory locations.
Let the differential cost function
Δ
ν
(
a
)
be defined as
For the matrix-matrix multiplication and FFT problems, the cost
Δ
ν
(
a
)=
ν
(
a
)
−
ν
(
a
−
1
)
As a consequence, we can write
ν
(
a
)
as follows if we set
ν
(
−
1
)=
0:
ν
(
a
)=
0
Δ
ν
(
b
)
(11.4)
≤b≤a
Since
ν
(
a
)
is a monotone nondecreasing function,
Δ
ν
(
m
)
is nonnegative.
Rewriting (
11.3
)using(
11.4
), we have
n
(
f
,
x
,
a
)
0
K
ν
(
f
)= max
x
Δ
ν
(
b
)
1
≤a
≤b≤a
=
max
x
n
(
f
,
x
,
d
)
∞
Δ
ν
(
c
)
∞
c
=
0
d
=
c
Δ
ν
(
c
)
max
x
n
(
f
,
x
,
d
)
=
∞
∞
(11.5)
c
=
0
d
=
c
=
∞
Δ
ν
(
c
)
K
U
c
(
f
)
c
=
0
11.9.1 Lower Bounds for the HMM
Before deriving bounds on the cost to do a variety of tasks in the HMM, we introduce the
binary search problem.
A
binary tree
is a tree in which each vertex has either one or two descendants except leaf
vertices, which have none. (See Fig.
11.17
.) Also, every vertex except the root vertex has one
9
6
13
3
7
11
17
1
5
8
15
20
Figure 11.17
A binary search tree.
Search WWH ::
Custom Search