What is the asymptotic complexity of T(n) = T(n-1) + O(n * n!)? A tight upper bound would suffice. I am trying to calculate the time complexity of a very elaborate recursive algorithm to find anagrams and eventually I came up on this formula (which is hopefully right). You can assume that the algorithm stops when it reaches T(1).
Edit: T(n) = T(n-1) + O(n * n!) equals of course O(n*n!) + O((n-1)*(n-1)!) + ... + O(1) but I don't know what to do with that.
To get a rigorous understanding of what's going on, note that
n * n! = (n + 1) * n! - n! = (n + 1)! - n!
Hence the original function can be rewritten as:
T(n) = T(n-1) + c * ((n + 1)! - n!) where c is a constant from the O(f(n)) notation
If you expand T(n-1) etc you'll see that the factorials cancel out giving finally
T(n) = T(0) + c * ((n + 1)! - 0!)
Hence if T(0) is constant and finite,
T(n) = O((n + 1)!)