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.


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.

  • $\begingroup$ That makes sense. Thanks for your input. $\endgroup$ – Saftkeks Aug 28 '19 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$ – Saftkeks Aug 28 '19 at 15:13
  • $\begingroup$ Yes, if $L$ is fixed (or bounded above by some constant) then $|P|^L$ is polynomial. $\endgroup$ – David Richerby Aug 28 '19 at 15:35

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.