This is the archived version of this course from the Spring 2013 semester. You might find something more recent by visitning my teaching page.
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\).