0
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.