How to solve the recurrence: T(n) = n*T(n-1) + n?

Question

In a an exercise I'm required to analyze the runtime of recursive function:

 foo(n)
     for i from 1 to n
         work() // O(1)
         foo(n-1)
     end for
 end foo

The recurrence relation I understand from the code is: T(n) = n*T(n-1) + n

But I'm failing trying to analyze it using the iterative method since I don't see a repeating pattern when I'm opening some of the terms

How do I solve this recurrence ?

Answer 1

Looks like $$ T(n) = n! + \left(\frac{n!}{0!} +\frac{n!}{1!} +\frac{n!}{2!} +\frac{n!}{3!} + \dots + \frac{n!}{(n-2)!} + \frac{n!}{(n-1)!}\right) $$ satisfies the recurrent relation (here $T(0) = 1$).

From this for example $T(n) \leq n!(1+e)$.

Answer 2

Looking for the pattern (aka "guess and prove") is definitely a workable approach here. Sometimes it's about arranging things in the right way in your head:

(Assuming $T(0) = 0$ as anchor.)

This path leads to an exact solution in terms of "well-known" functions, namely a sum of falling factorials if not a nice closed form. You'd then prove this guess correct using induction, which is elementary here.

---

Actually, there is a mechanical approach to solve this: using generating functions. Since clearly $T(n) \in \Omega(n!)$, we know we'll have to use exponential generating functions (at least). So, from the ansatz

$\qquad\displaystyle T(z) = \sum_{n \geq 0} t_n \cdot \frac{z^n}{n!} = \sum_{n \geq 1} n \cdot \frac{z^n}{n!} + \sum_{n \geq 1} n \cdot t_{n-1} \cdot \frac{z^n}{n!}$

we obtain, using elementary manipulation of sums/series, that

$\qquad\displaystyle T(z) = ze^z \cdot \frac{1}{1-z}$.

Inserting the well known series for $e^z$ and $(1-z)^{-1}$ and applying the (binomial) convolution, you get the same solution as "seen" above:

$\qquad\displaystyle t_n = \sum_{k=1}^{n} \frac{n!}{(n-k)!}$.

Now, we can rearrange:

$\qquad\displaystyle t_n \ =\ n! \cdot \sum_{k=1}^{n} \frac{1}{(n-k)!} \ =\ n! \cdot \sum_{k=0}^{n-1} \frac{1}{k!} \ \sim\ n! \cdot e$.