Problem 55

This is the archived version of this course from the Spring 2013 semester. You might find something more recent by visitning my teaching page.

# Game tree evaluation with branching factor 3

Due: March 22
Points: 3

In class and in the notes we analyzed the cost of randomized game tree evaluation with branching factor 2, and determined that it was $$\Theta(n^{\log_4 3})$$ expected time, which is approximately $$\Theta(n^{0.79})$$

What if the branching factor is 3 instead of 2? That is, each player in the game has 3 possible moves at every step. Come up with the asymptotic cost in terms of $$n$$, as we did for $$k=2$$.