# 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 $\displaystyle N_1=\sum_{i=1}^n(i+1)!$
Now this can also be expressed as $\displaystyle (n+1)!+n!+(n-1)! + \cdots + 2\ + 1$.
Now what is the complexity of the algorithm? Is it $\displaystyle \mathcal{O}(n+1)!$ ?
But is $\displaystyle N_1 = \mathcal{O}(n!)$ ?
Which raises the following question: Is $\displaystyle n!=\Theta((n+1)!)$ ?
Similarly, if $\displaystyle N_2=\sum_{i=1}^n i(i+1)$ then $\displaystyle N_2$ can be expressed as $\displaystyle n\cdot (n+1) + (n-1)\cdot n +\cdots + 2\cdot 3 + 1\cdot 2$.
Now is $\displaystyle N_2=\mathcal{O}(n^2)$ ?

Thanks!

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

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