so they can be made arbitrarily large, typically by playing them on an n-by-n board. (From the point of view of computational complexity, a game on a fixed size of board is a finite problem that can be solved in O(1), for example by a look-up table from positions to the best move in each position.)

The asymptotic complexity is defined by the most efficient algorithm for solving the game (in terms of whatever computational resource one is considering). The most common complexity measure,