Results 1 to 2 of 2

Thread: Asymptotic behavior of an expression

  1. #1
    Member
    Joined
    Jan 2010
    Posts
    133

    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!
    Last edited by rebghb; Oct 25th 2010 at 09:23 AM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,577
    Thanks
    790
    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)!)$.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Right end behavior modelss, HELP PLZ!
    Posted in the Calculus Forum
    Replies: 1
    Last Post: Mar 1st 2010, 02:24 AM
  2. Replies: 2
    Last Post: Dec 16th 2009, 02:49 AM
  3. Replies: 1
    Last Post: Oct 5th 2009, 12:39 PM
  4. function behavior
    Posted in the Calculus Forum
    Replies: 3
    Last Post: Aug 10th 2009, 01:46 AM
  5. asymptotic behavior of integral
    Posted in the Calculus Forum
    Replies: 6
    Last Post: Jun 18th 2008, 10:47 AM

Search Tags


/mathhelpforum @mathhelpforum