Game-tree complexity of a game is the number of leaf nodes in the smallest full-width decision tree that establishes the value of the initial position.
The computational complexity of a game describes the asymptotic difficulty of a game as it grows arbitrarily large, expressed in big O notation or as membership in a complexity class.
(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).
It is not obvious that there is any lower bound on the space complexity for a typical game, because the algorithm need not store game states; however many games of interest are known to be PSPACE-hard, and it follows that their space complexity will be lower-bounded by the logarithm of the asymptotic state-space complexity as well (technically the bound is only a polynomial in this quantity; but it is usually known to be linear).
For tic-tac-toe, a simple upper bound for the size of the state space is 39 = 19,683.
A natural generalization is to m,n,k-games: played on an m by n board with winner being the first player to get k in a row.
This places it in the important complexity class PSPACE; with more work, it can be shown to be PSPACE-complete.
[4] Due to the large size of game complexities, this table gives the ceiling of their logarithm to base 10.