What's the time complexity of Monte Carlo Tree Search?
According to http://stanford.edu/~rezab/classes/cme323/S15/projects/montecarlo_search_tree_report.pdf  


  Time Complexity
  The runtime of the algorithm can be simply be computed as
  $O(mkI/C)$
  where $m$ is the number of random children to consider per search and $k$ is the number of parallel searches, and
  $I$
  is the number of iterations and
  $C$
  is the number of cores available.  
  
  Memory Complexity
  The memory complexity is
  $O(mk)$ since in each iteration we map
  $mk$
  states over the cluster.