title: How do you derive the time complexity of alpha-beta pruning?
body: <p>I understand the basics of minimax and alpha-beta pruning. In all the literature, they talk about the time complexity for the best case is O(b^(d/2)) where b = branching factor and d = depth of the tree, and the base case is when all the preferred nodes are expanded first.</p>
  
  <p>In my example of the "best case", I have a binary tree of 4 levels, so out of the 16 terminal nodes, I need to expand at most 7 nodes. How does this relate to O(b^(d/2))? </p>
  
  <p>I don't understand how they come to O(b^(d/2)). </p>