What is the time complexity of $\sum_{i = 1}^n \mathcal{O}(n!)$? Consider the following recurrence:
\begin{equation*}
      T(n) = \begin{cases}
        \Theta(1) & \mbox{if $n = 1$}\\
        n \cdot T(n - 1) + \Theta(n) & \mbox{otherwise} \\
      \end{cases}
    \end{equation*}
From a high level, it can be guessed (after writing the recurrence tree) that the time complexity is $\mathcal{O}(n!)$. However, I am trying to derive the proof.
Here is how far I have got:
\begin{equation*}
      T(n) = \sum_{i = 1}^n \left(\Theta(i) \prod_{j = i}^n j\right) = \sum_{i = 1}^n \Theta(i) \left(\frac{n!}{i!}\right) =  \sum_{i = 1}^n \Theta\left(\frac{n!}{(i - 1)!}\right) = \sum_{i = 1}^{n}\mathcal{O}(n!)
    \end{equation*}
This finally boils down to the question, "what is the time complexity of $\sum_{i = 1}^n \mathcal{O}(n!)$?"
 A: First, here's two useful related answers over on StackOverflow:
https://stackoverflow.com/questions/39328651/is-my-function-on-or-is-on-1-more-accurate
https://stackoverflow.com/questions/35000930/which-big-o-grows-faster-asymptotically
In your case here, we can certainly bound the sum from above:
$$\sum_{i = 1}^n O(n!) = n * O(n!) \le (n+1) * O(n!) = \boxed{O((n+1)!)},$$
where we note that $O((n+1)!)$ is not equal to $O(n!)$, as $f(n) = (n+1)!$ is in $O((n+1)!)$, but
$$\lim_{n \rightarrow \infty} \frac{(n+1)!}{n!} = \lim_{n \rightarrow \infty} (n+1) = \infty,$$
so there are no constants $c, n_0$ such that $(n+1)! < c n!$ for all $n > n_0$, and so $f(n)$ is not in $O(n!)$.
However, the more interesting question is how tight we can make this bound. As you mentioned, your recurrence satisfies
$$T(n) = \sum_{i = 1}^n \Theta\left(\frac{n!}{(i-1)!}\right) = n! + \frac{n!}{2!} + ... + \frac{n!}{(n-1)!}.$$
Let's try and compare this against $O(n!)$. It seems to me that
$$\lim_{n \rightarrow \infty} \frac{T(n)}{n!} = \lim_{n \rightarrow \infty} \frac{1}{1!} + \frac{1}{2!} + ... + \frac{1}{(n-1)!} = e,$$
so we have that $T(n) = O(n!)$ after all! Combine this with the fact that $T(n)$ is asymptotically bounded below by $n!$ as well (i.e. $T(n) = \Omega(n!)$) and we have that $\boxed{T(n) = \Theta(n!)}$.
