title: Factorial running time
body: <p>When analyzing some code I've written, I've come up with the following recursive equation for its running time -</p>
  
  <p>T(n) = n*T(n-1) + n! + O(n^2).</p>
  
  <p>Initially, I assumed that O((n+1)!) = O(n!), and therefore I solved the equation like this - </p>
  
  <p>T(n) = n! + O(n!) + O(n^3) = O(n!)</p>
  
  <p>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.</p>
  
  <p>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.</p>
  
  <p>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...</p>
  
  <p>Any guidance would be much appreciated.</p>
  
  <p>Thank you!!!</p>