Information Technology Reference
In-Depth Information
lower bound:
ST
=Ω(
n
2
log
|R|
)
This lower bound can be achieved to within a constant multiplicative factor.
Proof
The upper bound follows by applying Lemma
10.9.3
and Theorem
10.5.5
.
10.13.7 Unique Elements
We now derive a lower bound on the space-time product for the sorting problem by reducing
sorting to the unique-elements problem. The unique elements problem takes a list of values
and returns in any order a list of the non-repeated elements among them.
DEFINITION
10.13.1
Let
R
be a set with at least
n
distinct elements. The function
f
(
n
)
unique
:
2
R
n
defines the
unique elements
problem where
2
R
n
n
n
R
→
is the power set of
R
and
f
(
n
)
unique
(
x
)
is the set of non-repeated elements in the input string
x
.
We emphasize that no order is imposed on the outputs of
f
(
n
)
unique
. Thus, if a set of values
appears in the output, their position in the output does not matter.
From Lemma
10.11.2
it follows that a lower bound to
ST
can be derived by restricting
the domain and discarding outputs. We restrict the domain by restricting each input variable
to values in a subset
S⊆R
containing
n
elements. We also restrict input tuples to the
set
containing at least
n/
(
2
e
)
unique values (
e
isthebaseofthenaturallogarithm). In
the following lemma we show that
D
|D| ≥ |S|
n
/
(
2
e
−
1
)=
φn
n
,where
φ
=
1
/
(
2
e
−
1
)
.
the function
f
(
n
)
On inputs in
D
unique
has at least
n/
(
2
e
)
unique outputs. We define the
subfunction
f
(
n
)
m
,
m
=
n/
(
2
e
)
,of
f
(
n
)
n
restricted
:
S
→S
unique
to be the subfunction obtained
n
and deleting all but the first
n/
(
2
e
)
outputs, which are all
D⊂S
by restricting its inputs to
unique.
LEMMA
10.13.6
Let
S
be a set of
n
elements. The fraction
φ
of the input
n
-tuples over
S
n
containing
n/
(
2
e
)
or more unique elements exceeds
1
/
(
2
e
1
)
.
Proof
We use simple probabilistic arguments. Assign each
n
-tuple over
−
n
probability
1
/n
n
.Let
u
(
x
)
be the number of unique elements in
x
.Let
X
i
(
x
)
have value 1 if the
i
th
element of
S
S
occurs uniquely in
x
and value 0 otherwise. Then
n
u
(
x
)=
X
i
(
x
)
i
=
1
Let
E
[
u
]
denote the average value of
u
(
x
)
(the sum of
u
(
x
)
over
x
weighted by its prob-
ability). Because the order of summation can be changed without affecting the sum, we
have
n
E
[
u
(
x
)] =
E
[
X
i
(
x
)]
i
=
1
E
[
X
i
(
x
)]
is also the probability that
X
i
=
1. If
X
i
=
1, then each of the other components
of
x
can assume only one of
n
−
1 values. Since the
i
thvaluecanbeinanyoneof
n
positions
Search WWH ::
Custom Search