It is very flaky to calculate this theoretically, as it's very implementation dependent. Depending on the spatial efficiency of the data structures, caching, and so on, it can vary from sublinear all the way to factorial.
Let me give you a few examples. In BnB, all we really need to store is the bounds of all variables for every node of the BnB tree. Ergo, the spatial complexity should be
However, we might also use some hash maps to look up information internally, and depending on the implementation this might scale cubicaly or worse. We might also use a git-style diff technique to only store bounds changes instead of actual bounds, which could reduce the average runtime complexity to sublinear.
Solvers being the complex pieces of software they are, other information might be stored, such as conflicts for conflict analysis, restoration information, and so on. For (MI)NLPs, the way the hessian is calculated can also affect memory usage considerably. For a good implementation that would have a constant spatial overhead (as in it doesn't scale with the number of nodes), but some solvers don't do this very well.
Solvers might also store warm starting information for some nodes (but not all of them), which can also induce a memory overhead that scales with the number of nodes in a non-obvious way (since it's governed by a heuristic).
Finally, if a solver generates cuts dynamically, then this also induces a hard to calculate memory overhead. There are typically limits on pool sizes and sizes of cuts, but these can also change on the fly depending on the implementation.
W.r.t. to your questions:
- What would happen if the complexity exceeds the machine capacity?
Typically the solver & the computer will crash. Some commercial solvers have ways around this, e.g. CPLEX can store part of the BnB tree on the hard drive for very large problems/trees.
- In this case, what would be the impact on the resolution time?
Assuming the computer doesn't crash, performance can be abysmal, but highly depends on implementation. For a bad implementation you would expect 100x-1000x worse performance. For a good implementation, it might only be 2x-5x worse.