minimax complexity has an upper bound complexity *of o(b^m)*, where b are the legal moves in the game and m the depth of the search tree.

For an unbounded tic-tac-toe search, the max depth would be 9, and the number of legal moves goes decreasing as the search deepens e.g. at depth 0 it’s 9, at depth 1 8 and so on. Thus the complexity should be *o(m!)*.

However my current implementation gives *434746* iterations to the minimax function (for the first movement), which leads me to think that my previous analysis is wrong. Any hints/ideas?

*9^9 > 434746 > 9!*