Asymptotic behavior of an expression

**rebghb** · October 25th 2010, 08:38 AM

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!

**emakarov** · October 25th 2010, 09:24 AM

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)!)$ .

Thread: Asymptotic behavior of an expression

LinkBack

Thread Tools

Display

Asymptotic behavior of an expression

Similar Math Help Forum Discussions

Right end behavior modelss, HELP PLZ!

Which of the following describes the behavior of y=(x+2)^(1/3(

Asymptotic behavior of the number of perfect squares less than x

function behavior

asymptotic behavior of integral

Search Tags