Assume $T(n) = \Theta(1)$ for $n \leq 1$. Using iterative substitution.
So far I have:
\begin{align*} &T(n) = nT(n - 1) + 1\\ &= n((n - 1)T(n - 2) + 1) + 1\\ &= n(n - 1)T(n - 2) + n + 1 \end{align*}
I'm stuck on how I'm supposed to get the asymptotic value from this. Or how would I keep expanding? Thanks!
On
As I've said here before, when a recurrence has a $n$ in it, $n!$ or $(n+1)!$ usually helps.
You have $T(n) = nT(n - 1) + 1 $.
After staring at this for a bit, I decide to divide by $n!$. This becomes $\frac{T(n)}{n!} = \frac{T(n - 1)}{(n-1)!} + \frac1{n!} $.
Letting $u(n) =\frac{T(n)}{n!} $, this becomes $u(n) =u(n-1)+\frac1{n!} $ or $u(n)-u(n-1)=\frac1{n!} $.
Summing from $2$ to $n$, $u(n)-u(1) =\sum_{k=2}^n \frac1{k!} $ so $u(n)=u(1)+\sum_{k=2}^n \frac1{k!} $.
Replacing $u(n) =\frac{T(n)}{n!} $, $\frac{T(n)}{n!}=T(1)+\sum_{k=2}^n \frac1{k!} $ or $T(n)=n!(T(1)+\sum_{k=2}^n \frac1{k!}) $.
Method 1: Iteration
What you have so far is good. Just keep going! Here are the next two iterations, to help you: \begin{align*} T(n) &= n(n-1)(n-2)T(n-3) + n(n-1) + n + 1 \\ T(n) &= n(n-1)(n-2)(n-3)T(n-4) + n(n-1)(n-2) + n(n-1) + n + 1 \end{align*}
Do you see the pattern? (It's not so obvious!)
Method 2: Generating Functions
Using the exponential generating function $F(x) = \sum_n T(n) x^n / n!$, from $$ T(n)\frac{x^n}{n!} = n T(n-1) \frac{x^n}{n!} + \frac{x^n}{n!} $$ we get $$ F(x) = xF(x) + e^x + T(0) - 1. $$ Therefore, with $c = T(0) - 1$, $$ F(x) = \frac{e^x + c}{1-x}. $$ It follows that the coefficient of $x^n$ is $$ c + \sum_{i=0}^n \frac{1}{i!} $$ so that $$ T(n) = cn! + \sum_{i=0}^n \frac{n!}{i!}. $$ In fact, for $n \ge 1$ the latter sum is less than $e \cdot n!$ but bigger than $e \cdot n! - 1$, and is also an integer. So we get $$ T(n) = c \cdot n! + \lfloor{e \cdot n!\rfloor}, $$ for $n \ge 1$. For $n = 0$, the floor formula does not work, and we just have $T(0) = c + 1$.