There are numerous notions of computability for non-standard structures, like higher order functions or real number computations. However, most of their underlying computational model lack a natural notion of complexity. Indeed, if we understand well what the complexity of a first order or even second order functions is, it is far from being the case for other, more complex objects.

I will describe a few existing computational models, especially for higher order functions, to see why they are not complexity-friendly. Then, I will propose a general framework based on game semantics to define meaningful notions of size and complexity for quite general objects and provide several examples to illustrate it.