Why is the time complexity of factorization $2^n$?

Question

Can somebody explain to me why, given the factor value N, the time complexity of a factorization algorithm (N / 2, N / 3, N / 4, ...) is $2^n$ rather than n?

Answer 1

The time complexity of factorization is $O(N)$*.

However, the complexity class of an algorithm is expressed in terms of the "input size". $N$ is not the input size, the number of (binary) digits $n$ required to express it is.

As $N\le 2^n$, the time complexity is $O(N) = O(2^n)$.

---

Note*: Assuming integer division is O(1).