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?
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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$.
answered Feb 7, 2014 at 23:13