I originally read that Alpha-Beta pruning has time complexity of $O(b\ ^{m/2}\ )$ with perfect ordering (where b = branching factor, m = maximum ply depth) but have recently come across claims that this can be reduced to $O(2\ ^{m/2}\ )$ with optimal ordering. Does anyone know of a proof for this claim?
Complexity of Alpha-Beta pruning with optimal move ordering
artificial intelligence;game theory