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

     for i from 1 to n
         work() // O(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 ?

  • $\begingroup$ Up to which precision are you expected to solve it? Can you solve it without the $+n$ term? $\endgroup$
    – Raphael
    Apr 27, 2017 at 21:18
  • $\begingroup$ We have collected some useful material here, but I think "guess & proof" is what your teachers expect here. Hint: falling factorials. $\endgroup$
    – Raphael
    Apr 27, 2017 at 21:22
  • $\begingroup$ @Raphael I guess lower and upper bound (theta), as well as figuring out how many times work() will be called as an expression of n $\endgroup$
    – shaqed
    Apr 27, 2017 at 21:23
  • $\begingroup$ So, asymptotics. Ironically, I think the exact figure (in non-closed form) is easier here than a "nice" asymptotic. $\endgroup$
    – Raphael
    Apr 27, 2017 at 21:23
  • 1
    $\begingroup$ Possible duplicate of Solving or approximating recurrence relations for sequences of numbers $\endgroup$ Apr 27, 2017 at 23:04

2 Answers 2


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)$.

  • $\begingroup$ And how do they get there? $\endgroup$
    – Raphael
    Apr 27, 2017 at 22:35

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:

enter image description here
(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$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.