Information Technology Reference
In-Depth Information
that
k
=
1
K
U
2
k
(
f
)
t
K
ν
(
f
)=
(11.6)
for the task characterized by
f
,where
t
satisfies 2
t
≤
N
and
N
is the space used by task.
n
matrix multiplication,
N
=
n
for the FFT graph
F
(
d
)
,and
N
=
n
for
N
=
2
n
2
for
n
×
binary search.
In Theorem
11.5.3
it was shown that the number of I/
O
operations to perform
n
n
matrix multiplication with the classical algorithm is
Ω(
n
3
/
√
m
)
. The model of this theorem
assumes that none of the inputs are in the primary memory, the equivalent of the first
m
memory locations in the HMM.
Since no charge is assessed by the
U
m
(
a
)
cost function for data in the first
m
memory
locations, a lower bound on cost with this measure can be obtained from the lower bound
obtained with the red-blue pebble game by subtracting
m
to take into account the first
m
I/O operations that need not be performed.
Thus for matrix multiplication,
×
A×B
)=Ω
(
n
3
/
√
m
)
m
.Since
K
U
m
(
f
(
n
)
−
n
3
/
√
m
−
(
√
8
1
)
n
3
/
√
8
m
m
≥
−
A×B
)=Ω(
n
3
)
because
k
=
0
n
3
/
2
k
=
K
ν
(
f
(
n
)
n
2
/
2, it follows from (
11.6
)that
when
m
≤
Ω(
n
3
)
.
For the same reason,
K
U
m
(
F
(
d
)
)=Ω((
n
log
n
)
/
log
m
−
m
)
(see Theorem
11.5.5
)
K
ν
(
F
(
d
)
)
and
(
n
log
n/
log
m
)
−
m
≥
n
log
n/
(
2
log
m
)
for
m
≤
n/
2. It follows that
satisfies
K
ν
(
F
(
d
)
)=Ω
k
n
log
n
log(
2
k
)
=Ω
log
n
=Ω(
n
log
n
log log
n
)
n
log
n
k
k
=
1
The last equation follows from the observation that
k
=
1
1
/k
is closely approximated by
p
1
1
x
dx
,whichis
ln
p
. (See Problem
11.2
.)
The lower bound for comparison-based sorting uses the
Ω(
n
log
n/
log
m
)
sorting lower
bound for the BTM with a block size
B
=
1. Since the BTM assumes that no data are res-
ident in the primary memory before a computation begins, the lower bound for the HMM
cost under the
U
m
cost function is
Ω((
n
log
n/
log
m
)
−
m
)
. Thus, the FFT lower bound
appliesinthiscaseaswell.
Finally, we show that the lower bound for binary search is
K
U
m
(
f
(
n
)
BS
)=Ω(log
n
−
log
m
)
. Each path in the balanced binary search tree has length
d
=
log(
n
+
1
)
/
2
or
d
1. Choose a query path that visits the minimum number of variables located in the first
m
memory locations. To make this minimum number as large as possible, place the items
in the first
m
memory locations as close to the root as possible. They will form a balanced
binary subtree of path length
l
=
−
log
2
(
m
+
1
)
/
2
or
l
−
1. Thus no full path will have
more than
l
edges and
l
1 variables from the first
m
memory locations. It follows that
there is a path containing at least
d
−
−
1
−
(
l
−
1
)=
d
−
l
=
log(
n
+
1
)
−
log(
m
+
1
)
Search WWH ::
Custom Search