Consider a problem with two inputs like (P,L) and |P|=n and L is some positive integer. If my algorithm had a complexity of O(n^L), would that still be polynomial? Or is it exponential? I'm not sure if I should view L as a constant or as 'size of input', since it's not a size but just some number (as in, Knapsack for example, select items of weight <= L). At the same time, L is part of the input and not fixed.
1
-
$\begingroup$ I think you should take a look at this link. cs.stackexchange.com/questions/909/… $\endgroup$– Amar SharmaCommented Aug 28, 2019 at 13:28
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
3
You're confused because you've called part of your input $n$. When we say that the running time is some function of $n$, we almost always mean that $n$ is the length of the input string.
Your algorithm runs in time $|P|^L$, where $P$ is a string contained in the input and $L$ is a number represented in the input, presumably in binary. If $L$ is a $b$-bit number, it could be as big as $2^b$. Writing $n$ for the length of the input, we could, for example, have $|P|=n/2$ with $L$ being an $(n/2)$-bit number. That case gives running time $(n/2)^{2^{n/2}}$, which is a long, long way from being polynomial.
answered Aug 28, 2019 at 14:10
-
$\begingroup$ That makes sense. Thanks for your input. $\endgroup$– SaftkeksCommented Aug 28, 2019 at 14:55
-
$\begingroup$ if I understand this correctly, limiting L to be "some constant" would then make the input pseudopolynomial? To be more specific, I have a set of n nodes and I need to select the <= L nodes to optimize some other value, which means that brute force just tests all sets of size <= L $\endgroup$– SaftkeksCommented Aug 28, 2019 at 15:13
-
$\begingroup$ Yes, if $L$ is fixed (or bounded above by some constant) then $|P|^L$ is polynomial. $\endgroup$ Commented Aug 28, 2019 at 15:35