# Does 'subexponential algorithm' refer to input or number of bits used to represent input?

When an algorithm is said to be subexponential - does this refer to the input N or the number of bits used to represent N? Consider the following: trial division for integer factorization (i.e. try all numbers less than $\sqrt N$) is subexponential in terms of N.

Note: here I'm using the definition of 'subexponential' to be $2^{O(n^\epsilon)}$ for some $\epsilon < 1$.

That is it takes $2^{\log_2 \sqrt N}$ steps to factor N. This is obviously subexponential in terms of N. However, in terms of the number of bits B needed to represent N this is $2^{\frac B 2}$ which is not subexponential in terms of B.

So would trial division be considered subexponential or not? Or would it be considered both depending on whether you're referring to N or B?

Trial division is exponential: its running time is $O(N^{1/2})$, i.e., $O(2^{B/2})$ where $B=\lg N$ is the length of the input in bits. That's an exponential function (of $B$). See Are there subexponential-time algorithms for NP-complete problems?.
Not all algorithms are about numbers, so it doesn't always make sense to interpret the input string as a number and express the running time in terms of that number. If your algorithm is about graphs, then its input might be a string of $n^2$ zeroes and ones for a graph of $n$ vertices. Then if it runs in time $n^3$, we say it runs in time $O(n^3)$ or time $O(|V|^3)$ or $O(b^{\frac{3}{2}})$ if $b=n^2$ is the size of the input. If the input to an algorithm is a set of numbers, such as in the subset sum problem or the knapsack problem, the size of the input depends on the amount of numbers, and the size of those numbers, so the input may be expressed in terms of both the number of variables and their length. Indeed the best known algorithm, due to Horowitz and Sahni, runs in time $O(b\cdot 2^{\frac{1}{2}n})=O(b\cdot 2^{\frac{1}{2}b})$ for instances with $n$ variables, taking up in total $b$ bits. (somebody may correct me if I'm wrong)