3
$\begingroup$

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 ?

$\endgroup$
  • $\begingroup$ Up to which precision are you expected to solve it? Can you solve it without the $+n$ term? $\endgroup$ – Raphael Apr 27 '17 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 '17 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 '17 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 '17 at 21:23
  • 1
    $\begingroup$ Possible duplicate of Solving or approximating recurrence relations for sequences of numbers $\endgroup$ – David Richerby Apr 27 '17 at 23:04
2
$\begingroup$

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

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

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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