it's my first answer here. I do have an algorithm to calculate the factorial of a given number $n$ recursively, but without using any multiplication like the usual one, only sums are available. I've ended up with an algorithm with a complexity function $T(n) = 1 + nT(n - 1)$.Opening the recurrence relation ends up in:$T(n) = 1 + n T(n - 1)$$T(n) = 1 + n[1 + (n - 1)T(n - 2)]$$T(n) = 1 + n + n^2 T(n - 2) - n T(n - 2)$$T(n) = 1 + n + n^2[1 + (n - 2) * T(n - 3)] - n T(n - 2)$$T(n) = 1 + n + n^2 + n^3T(n - 3) - n T(n - 2) - n^2T(n - 3)$Because of the subtractions, I'm not able to reach good upper-bound for $T(n)$. Any tips ?Before asking the question, I've managed to state that $T(n) \in \mathcal{O}(n^n)$. Which is 'loose' upper bound, but I'm neither able to figure out a tighter upper bound.
A better upper bound to a recursive function
recurrence relation;recursion
Solving your recurrence, assuming the base case $T(0) = 1$, we get$$\begin{align*}T(n) &= 1 + nT(n-1) \\ &=1 + n + n(n-1)T(n-2) \\ &=1 + n + n(n-1) + n(n-1)(n-2)T(n-3) \\ &= \cdots \\ &=1 + n + n(n-1) + \cdots + n(n-1)\cdots2 + n! \\ &=n! \left(\frac{1}{0!} + \frac{1}{1!} + \frac{1}{2!} + \frac{1}{3!} + \cdots + \frac{1}{n!}\right) \\ &=n! \left(e - O\left(\frac{1}{(n+1)!}\right)\right) \\ &= e \cdot n! - O\left(\frac{1}{n}\right).\end{align*}$$In particular, $T(n) = \Theta(n!) = \Theta(\sqrt{n}(n/e)^n)$.