Could prime factorization of n!+1 using the general number field sieve be said to take subfactorial time?

Question

I am interested in the prime factorization using the general number field sieve. This method is said to take subexponential time relative to the number of bits in a number. (Other algorithms are exponential.) I have two questions about this:

1. Could this operation be said to take subfactorial time?
2. Does this operation on average take greater than exponential time? If so, then it is between exponential and factorial.

Answer 1

For a number $n$ that has $b=1+\log_2 n=O(\ln n)$ bits NFS has complexity of the order $$ \exp\left\{(c+o(1)) (\ln n)^{1/3} (\ln \ln n)^{2/3}\right\} $$

which is subexponential when compared to the input size in bits. An exponential algorithm would have complexity of the order $$ \exp(c b)=\exp(c \ln n). $$

If the unusual term factorial time means an algorithm takes time asymptotic to $\ln b!$ for the input size $b$ the answers to your questions are both yes.