# Complexity Class of an Algorithm with two Inputs

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.
• Yes, if $L$ is fixed (or bounded above by some constant) then $|P|^L$ is polynomial. Aug 28 '19 at 15:35