Factorial running time

Question

When analyzing some code I've written, I've come up with the following recursive equation for its running time -

T(n) = n*T(n-1) + n! + O(n^2).

Initially, I assumed that O((n+1)!) = O(n!), and therefore I solved the equation like this -

T(n) = n! + O(n!) + O(n^3) = O(n!)

Reasoning that even had every recursion yielded another n! (instead of (n-1)!, (n-2)! etc.), it would still only come up to n*n! = (n+1)! = O(n!). The last argument is due to sum of squares.

But, after thinking about it some more, I'm not sure my assumption that O((n+1)!) = O(n!) is correct, in fact, I'm pretty sure it isn't.

If I am right in thinking I made a wrong assumption, I'm not really sure how to actually solve the above recursive equation, since there is no formula for the sum of factorials...

Any guidance would be much appreciated.

Thank you!!!

Answer 1

Since you're looking at run-time, I assume O(n^2) is meant to be the number of operations on that term. Under that assumption, n! can be computed in O(n) time (1*2*3*...*n). So, it can be dropped in comparison to the O(n^2) term. T(n-1) is then computed in approximately O((n-1)^2) time which is roughly O(n^2). Putting it all together you have something which runs in

O(n^2) + O(n) + O(n^2)

resulting in an O(n^2) algorithm.