HiveBrain v1.2.0
Get Started
← Back to all entries
snippetMinor

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

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
thesolverecurrencehow

Problem

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 ?

Solution

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

Context

StackExchange Computer Science Q#74631, answer score: 2

Revisions (0)

No revisions yet.