Results 1 to 2 of 2

Math Help - Big oh problem

  1. #1
    Newbie
    Joined
    Oct 2009
    Posts
    3

    Big oh problem

    I couldn't solve this one ?

    What is the Big O of this function ?

    Void two(int n)
    {
    int
    i,j,k,n;

    for
    (i=1;i<=n;i++)
    for (j=(i+1);j<=n;j++)
    for (k=1;k<=j;k++)

    o(1) statment;

    }
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by Acessd23 View Post
    I couldn't solve this one ?

    What is the Big O of this function ?

    Void two(int n)
    {
    int
    i,j,k,n;

    for
    (i=1;i<=n;i++)
    for (j=(i+1);j<=n;j++)
    for (k=1;k<=j;k++)

    o(1) statment;

    }
    The loop operations count of the inner most loop is o(1)j, so that of the next outer loop is:

    \sum_{j=i+1}^n o(1)j

    ans so for the outermost loop:

    \sum_{i=1}^n \left[ \sum_{j=i+1}^n o(1)j\right]=o(1)\sum_{i=1}^n \left[ \sum_{j=i+1}^n j\right]

    CB
    Follow Math Help Forum on Facebook and Google+

Search Tags


/mathhelpforum @mathhelpforum