Results 1 to 2 of 2

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

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,527
    Thanks
    773
    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)!).
    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: March 1st 2010, 02:24 AM
  2. Replies: 2
    Last Post: December 16th 2009, 02:49 AM
  3. Replies: 1
    Last Post: October 5th 2009, 12:39 PM
  4. function behavior
    Posted in the Calculus Forum
    Replies: 3
    Last Post: August 10th 2009, 01:46 AM
  5. asymptotic behavior of integral
    Posted in the Calculus Forum
    Replies: 6
    Last Post: June 18th 2008, 10:47 AM

Search Tags


/mathhelpforum @mathhelpforum