How to analyse the complexity of a problem with two or more size measures Consider this example: a problem of dimension $n$ and $m$ ($m,n$: any given integers).
has a search space of size $O(n^n * m^n)$. 
It is clear that this problem is exponential in $n$,
whatsoever $m$ may be.
My question: is this same problem polynomial in $m$? 
what are the assumptions if we can say that?
is this way of complexity analysis correct?
There's nothing wrong with your approach. You have a two-variable function with a known (almost, up to a multiplicative constant) upper bound. In that case, it's perfectly acceptable to take a "slice" through the function by holding one of the variables fixed and ask how the resulting one-variable function behaves. One does this sort of thing often, when, for example, we take the derivative of $f(x, y)$ with respect to $x$.