Hardware Reference
In-Depth Information
Hence, Equation (9.4) is equivalent to
⎧
⎨
C
0
=1
C
1
=
k
−
1
(9.6)
⎩
C
i
+2
=
k
(
C
i
+1
−
C
i
)
.
From this result, we can say that the tightest bound on the competitive factor of an
online algorithm is given by the smallest ratio 1
/k
(equivalently, the largest
k
) such
that (9.6) satisfies (9.5). Equation (9.6) is a recurrence relation that can be solved by
standard techniques [Sha85]. The characteristic equation of (9.6) is
x
2
−
kx
+
k
=0
,
which has roots
x
1
=
k
+
√
k
2
−
√
k
2
−
4
k
k
−
4
k
and
x
2
=
.
2
2
When
k
=4,wehave
C
i
=
d
1
i
2
i
+
d
2
2
i
,
(9.7)
and when
k
=4we have
=
d
1
(
x
1
)
i
+
d
2
(
x
2
)
i
,
C
i
(9.8)
where values for
d
1
and
d
2
can be found from the boundary conditions expressed in
(9.6). We now show that for (
k
=4) and (
k>
4)
C
i
will diverge, so Equation (9.5)
will not be satisfied, whereas for (
k<
4)
C
i
will satisfy (9.5).
Case (
k
=4
)
. In this case,
C
i
=
d
1
i
2
i
+
d
2
2
i
, and from the boundary conditions, we
find
d
1
=0
.
5 and
d
2
=1. Thus,
C
i
=(
i
2
+1)2
i
,
which clearly diverges. Hence, for
k
=4, Equation (9.5) cannot be satisfied.
Case (
k>
4
)
. In this case,
C
i
=
d
1
(
x
1
)
i
+
d
2
(
x
2
)
i
, where
k
+
√
k
2
−
√
k
2
−
4
k
x
2
=
k
−
4
k
x
1
=
and
.
2
2
From the boundary conditions we find
C
0
d
1
+
d
2
=1
=
C
1
=
d
1
x
1
+
d
2
x
2
=
k
−
1;
Search WWH ::
Custom Search