Game Development Reference
InDepth Information
In order to achieve the worstcase running time bound
O
(
n
d/
3+
O
(1)
) for
the modified divideandconquer algorithm
paritywindominion
†
(
G
), we
have to make an appropriate choice of the parameter
b
for the calls to the
preprocessing procedure
progressmeasurelifting
†
(
G, b
). It turns out that a
good choice for the analysis of the modified algorithm is
b
=2
n
2
/
3
, where
n
is the number of vertices of the parity game in the toplevel call of the
algorithm
paritywindominion
†
(
G
).
Note that in order to facilitate the runningtime analysis of the algorithm,
the choice of the parameter
b
is fixed globally for all recursive calls. This is
unlike procedure
paritywindominion
(
G
), in which the parameter
has been
always the function of the number of vertices in the actual argument
G
of
each recursive call. It is worth noting that the analysis of the running time
of the algorithm
paritywindominion
(
G
) carried out in Section 3.3.2 could
have also been done with the parameter
fixed at the top level throughout
all recursive calls.
In the following exercise we analyse the worstcase running time of the
preprocessing procedure
progressmeasurelifting
†
(
G, b
).
=
b
+(
d/
2)
d/
2
=
d/
2
b
+
i
Exercise 3.23
Argue that

N
b

i
. Prove that for all
i
=1
n
2
/
3
b
+1
1
b
+2
2
b
+3
3
b
+4
4
su
ciently large integers
n
,if
b
=2
then we have
·
·
·
≤
(
n
2
/
3
)
4
, and
i
≤ n
2
/
3
for all
i ≥
3, and hence that
N
b
≤n
d/
3
for all
d ≥
8.
Conclude that if
b
(
n
)=2
b
+
i
n
2
/
3
then the worstcase running time of the
procedure
progressmeasurelifting
†
(
G, b
(
n
)) is
O
(
n
d/
3+
O
(1)
).
We are now ready to complete the analysis of the worstcase running
time of the divideandconquer algorithm
paritywindominion
†
(
G
). Observe
that if the
else
case in the algorithm
paritywindominion
†
(
G
) obtains then
the argument of the only recursive call
paritywindominion
†
(
G
∗
) is clearly
a game with no more than
n
n
2
/
3
vertices. On the other hand, if the
then
case obtains instead, then within the call
paritywin
‡
(
G
∗
) two recursive
calls
paritywindominion
†
(
G
) and
paritywindominion
†
(
G
) are made, the
argument
G
of the former has at most
d −
1 priorities if
G
had
d
, and the
number of vertices of the argument
G
of the latter is, by Exercise 3.22, at
most
n−n
2
/
3
−
decrease in size of game
G
∗
or
of
G
, at most one recursive call is made to a game with at most
d
. In either case, for every
n
2
/
3
1 priorities.
Finally, each recursive call of procedure
paritywindominion
†
(
G
) leads to
one call of procedure
progressmeasurelifting
†
(
G, b
) which, by Exercise 3.23,
runs in time
O
(
n
d/
3+
O
(1)
).
−
Exercise 3.24
Argue that the worstcase running time of the procedure
Search Nedrilad ::
Custom Search