I'm sorry for reviving an old question, but I think a mistake might be made here that is repeated over and over.
As far as I know, computational complexity is defined over the size of an efficient encoding of the input (
Given an input number
m for for factorial, it is true that the algorithm requires
But this is not of linear order (i.e. the same order as the size of the encoded input), because an efficient encoding of a number
m is of size
n := log m
This means that the time complexity indeed IS exponential (
m = 2^n multiplications) in the size of (an efficient encoding of) the input!
m multiplications are only linear in the input if you choose a unary encoding of the input, which is not an "efficient" choice.