Game Development Reference
InDepth Information
to have worstcase running time
O
(
n
). Note that in order to achieve this
running time it is su
cient to consider a naive bruteforce search solution that
(i) generates all
n
sets of vertices of size at most
, and (ii) for each of them
verifies if they are 0closed or 1closed, and runs the
O
(2
) divideandconquer
algorithm to check if they are a 0dominion or a 1dominion.
Exercise 3.14
Assume that a bruteforce search
O
(
n
)time implementa
tion of procedure
dominion
(
G,
) is used. Argue that the worstcase running
time of the algorithm
paritywindominion
(
G
) can be characterised by the
recurrence:
(
n
)) +
O
(
n
(
n
)
)
,
T
(
n
)
≤
T
(
n
−
1) +
T
(
n
−
(3.3)
T
(1) =
O
(1)
.
First, argue that the worst case is when the
paritywin
†
(
G
) call is made in
procedure
paritywindominion
(
G
), and then both
paritywindominion
(
G
)
and
paritywindominion
(
G
) calls are made in procedure
paritywin
†
(
G
).
Then, argue that since the set
reach
i
(
W
i
)isan
i
dominion in game
G
, and
since there is no dominion of size at most
in
G
, it must be the case that
the number of vertices in game
G
=
G
reach
i
(
W
i
) is at most
n
\
−
(
n
).
It turn
s o
ut that if the maximum size
(
n
) of dominions sought is chosen
to be
√
2
n
is the number of vertices, then the size of the
tree of r
ec
ursive calls of algorithm
paritywi
n
dominion
(
G
) can be bounded
by
n
O
(
√
n
)
. It then follows that
T
(
n
)=
n
O
(
√
n
)
.
, where
n
=

V

Exercise 3.15
For every positive integer
n
, construct a labelled binary
tree
τ
n
in the following way. The root of
τ
n
is labelled by
n
. A node labelled
byanumber
k>
3 has two
ch
ildren: a left child labelled by
k
−
1 and a
−
√
2
k
right child labelled by
k
. Nodes labelled by numbers 1, 2, and 3 are
leaves.
Prove th
at o
n every path from the root of
τ
n
to one of its leaves there are
at most
√
2
n
1
2
j
2
<n
right
tu
rns. Use induction and the fact that if
≤
−
√
2
n
1
1
2
(
j
+1)
2
then
n
2
j
2
. Conclude that the number of leav
es o
f
τ
n
is
≤
√
2
n
n
O
(
√
n
)
, and
th
at if the function
T
(
n
) satisfies (3.3) for
(
n
)=
then
T
(
n
)=
n
O
(
√
n
)
.
Theorem 3.8
(Jurdzinski et al. [2008])
The winning sets and positional
winn
in
g strategies of both players in parity games can be computed in time
n
O
(
√
n
)
.
Search Nedrilad ::
Custom Search