Information Technology Reference
In-Depth Information
b := 0;
for j:= 1 to
n/S
{
b =( j
1 ) S on the j th iteration.
}
begin
for i:= 1 to S
C [ i ]:= 0;
for i:= 1 to n
if b
x i
b + S then
begin
k := x i
b ;
if C [ k ] < 2 then C [ k ] := C [ k ]+ 1;
end ;
for i:= 1 to S
if C [ i ]= 1 then print b + i ;
b := b + S ;
end
Figure 10.22 A RAM program for the unique-elements problem over the set
{
1, 2, ... , n}
when n ≥ S ≥ O (log n ) . The input to the program is the n -tuple
x
in which x i
is the i th
entry. The program uses space O ( S ) .
Invoking Theorem 10.11.1 , we have a quadratic space-time product lower bound. The
RAM program for the unique elements problem given in Fig. 10.22 can be converted to a
branching program to obtain an upper bound on the space-time product needed for this
problem, as shown in Theorem 10.13.8 .
THEOREM 10.13.8 Let |R| ≥ n . There is an integer n 0 > 0 such that for n ≥ n 0 and
S =Ω(log n ) the time T and space S used by any general branching program for the unique
elements function f ( n )
2 R n must satisfy
n
unique :
R
ST =Ω( n 2 )
This lower bound can be met to within a constant multiplicative factor for inputs drawn from the
set
{
1, 2, 3, ... , n
}
.
Proof The lower bound follows directly from Theorem 10.11.1 . The upper bound follows
from an analysis of the branching program that results from conversion of the RAM program
in Fig. 10.22 .TheRAMprogrammakes
passes over the input data. On the j th pass
the program examines input values in the range [( j
n/S
1 ) S , ... , jS ] and determines for each
value whether there are zero, one, or more than one instances of it in the input.
The program uses an S -element one-dimensional array C [ 1 ..S ] that it initializes to zero
at the beginning of each pass. If on the j th pass the i th input variable, x i ,isintheinterval
[( j
1 ) S ] ,is
incremented unless it already has value 2. At the end of the j th pass, if the array element
C [ i ] has value 1, the program prints out the value jS + i , namely, the value of an input that
appears only once in the input.
1 ) S , ... , jS ] , the array element associated with it, namely C [ x i
( j
Search WWH ::




Custom Search