3
$\begingroup$

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.)?

$\endgroup$
4
$\begingroup$

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$.

$\endgroup$

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.