snippetMinor
How to solve the recurrence: T(n) = n*T(n-1) + n?
Viewed 0 times
thesolverecurrencehow
Problem
In a an exercise I'm required to analyze the runtime of recursive function:
The recurrence relation I understand from the code is:
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 ?
foo(n)
for i from 1 to n
work() // O(1)
foo(n-1)
end for
end fooThe recurrence relation I understand from the code is:
T(n) = n*T(n-1) + nBut 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)$.
$$
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.