Thread: Asymptotic behavior of an expression

1. Asymptotic behavior of an expression

Hello everyone!

I've been working on analyzing an algorithm and found that it requires performing $N_1=\sum_{i=1}^n(i+1)!$
Now this can also be expressed as $(n+1)!+n!+(n-1)! + \cdots + 2\ + 1$.
Now what is the complexity of the algorithm? Is it $\mathcal{O}(n+1)!$ ?
But is $N_1 = \mathcal{O}(n!)$ ?
Which raises the following question: Is $n!=\Theta((n+1)!)$ ?
Similarly, if $N_2=\sum_{i=1}^n i(i+1)$ then $N_2$ can be expressed as $n\cdot (n+1) + (n-1)\cdot n +\cdots + 2\cdot 3 + 1\cdot 2$.
Now is $N_2=\mathcal{O}(n^2)$ ?

Thanks!

2. We have $n!+(n-1)!+\dots+1\le n\cdot n!<(n+1)!$, so $\sum_{i=1}^n(i+1)!=O((n+1)!)$.

On the other hand, $(n+1)!$ is not $O(n!)$ because $(n+1)!/n!\to_{n\to\infty}\infty$. So, $n!$ is not $\Theta((n+1)!)$.