# Why is the complexity of factorial a function of n?

When we compute the complexity of calculating factorial of a number $n$ why is it in terms of $n$ instead of the number of the number of bits occupied by the number of bits occupied by $n$ (like we do in number-theoretic algorithms like primality checking etc.)?

## 1 Answer

Complexity can be expressed in terms of any reasonable measure. For example, when discussing graph algorithms, we usually state the complexity in terms of the number of vertices and/or edges, rather than the number of bits required to write the graph as input, e.g., as an adjacency matrix.

So I guess you've just come across resources that discuss the complexity in terms of the number being "factorialed" rather than the number of bits required to write down that number – I'm sure you'll agree that this is a reasonable measure, even if it's not your favourite one. Further, it's easy to convert between the two: a $k$-bit number can represent values up to $2^k$, so just take the expression you've been given and substitute $2^n$ for $n$.