I'm looking into the solution to this recurrence
T(n) = (n-1)T(n-1) + n
I'm about 90% sure that O(n!) is the correct answer except I'm having real trouble wrapping my head around a proof.
I can use the substitution method in this manner:
Guess that T(n) = O(n!)This implies that T(n) <= cn!From here we assume T applies to m < nAnd here we can use m = n - 1Which yields T(n - 1) <= c(n-1)!Plugging this back in to the recurrence gives usT(n) <= (n-1)*c(n-1)! + n <= (nc - c)(n-1)! + n <= nc(n-1)! - c(n-1)! + n <= cn! - c(n-1)! + n <= cn!Reduction to last line works when c >= 1
This works , right?