A better upper bound to a recursive function
Solving your recurrence, assuming the base case $T(0) = 1$, we get
$$
\begin{align*}
T(n) &amp;= 1 + nT(n-1) \\ &amp;=
1 + n + n(n-1)T(n-2) \\ &amp;=
1 + n + n(n-1) + n(n-1)(n-2)T(n-3) \\ &amp;= \cdots \\ &amp;=
1 + n + n(n-1) + \cdots + n(n-1)\cdots2 + n! \\ &amp;=
n! \left(\frac{1}{0!} + \frac{1}{1!} + \frac{1}{2!} + \frac{1}{3!} + \cdots + \frac{1}{n!}\right) \\ &amp;=
n! \left(e - O\left(\frac{1}{(n+1)!}\right)\right) \\ &amp;= e \cdot n! - O\left(\frac{1}{n}\right).
\end{align*}
$$
In particular, $T(n) = \Theta(n!) = \Theta(\sqrt{n}(n/e)^n)$.