Results 1 to 6 of 6

Math Help - Matlab - Determining the complexity of an algorithm

  1. #1
    Bar0n janvdl's Avatar
    Joined
    Apr 2007
    From
    South Africa
    Posts
    1,630
    Thanks
    6

    Matlab - Determining the complexity of an algorithm

    Hey everyone

    I'm trying to determine the complexity of the following algorithm:

    Code:
    A = 0:n;
    for i = 0:n-1
        s = 0;
        for j = 1:i
            s = s + X(j);
        end
        
        A(i+1) = s / (i+1);
    end
    I came up with the following:

    f(n) = \sum^{n-1}_{i = 0} \left( \left( \sum^{i}_{1} (1) \right) + 2 \right) + 1

    f(n) = \sum^{n-1}_{i = 0} \left( i \right) + 2n + 1

    f(n) =  \left( n \right) + 2n + 1

    f(n) =  3n + 1

    But something doesn't seem right here, since I've got a double for-loop. Shouldn't I be getting an n^2 ?

    Also, I'm supposed to find the complexity of the algorithm theoretically and practically. What exactly is the difference between the algorithm on paper and after I've coded it? The instructions are exactly the same.
    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 janvdl View Post
    Hey everyone

    I'm trying to determine the complexity of the following algorithm:

    Code:
    A = 0:n;
    for i = 0:n-1
        s = 0;
        for j = 1:i
            s = s + X(j);
        end
     
        A(i+1) = s / (i+1);
    end
    I came up with the following:

    f(n) = \sum^{n-1}_{i = 0} \left( \left( \sum^{i}_{1} (1) \right) + 2 \right) + 1

    f(n) = \sum^{n-1}_{i = 0} \left( i \right) + 2n + 1

    f(n) = \left( n \right) + 2n + 1

    f(n) = 3n + 1

    But something doesn't seem right here, since I've got a double for-loop. Shouldn't I be getting an n^2 ?

    Also, I'm supposed to find the complexity of the algorithm theoretically and practically. What exactly is the difference between the algorithm on paper and after I've coded it? The instructions are exactly the same.
    \sum_{i=0}^n i = \frac{n(n+1)}{2}

    CB
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Bar0n janvdl's Avatar
    Joined
    Apr 2007
    From
    South Africa
    Posts
    1,630
    Thanks
    6
    Quote Originally Posted by CaptainBlack View Post
    \sum_{i=0}^n i = \frac{n(n+1)}{2}

    CB
    Since the upper bound is n-1 will the result then be as follows?
    \sum_{i=0}^{n-1} i = \frac{n(n-1)}{2}
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Moo
    Moo is offline
    A Cute Angle Moo's Avatar
    Joined
    Mar 2008
    From
    P(I'm here)=1/3, P(I'm there)=t+1/3
    Posts
    5,618
    Thanks
    6
    Quote Originally Posted by janvdl View Post
    Since the upper bound is n-1 will the result then be as follows?
    \sum_{i=0}^{n-1} i = \frac{n(n-1)}{2}
    Yes.

    If you prefer, you can view that this way :
    \sum_{i=0}^{k} i=\frac{k(k+1)}{2}

    Then let k=n-1
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Bar0n janvdl's Avatar
    Joined
    Apr 2007
    From
    South Africa
    Posts
    1,630
    Thanks
    6
    Thanks for the help CB and Moo
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Bar0n janvdl's Avatar
    Joined
    Apr 2007
    From
    South Africa
    Posts
    1,630
    Thanks
    6
    Quote Originally Posted by Moo View Post
    Yes.

    If you prefer, you can view that this way :
    \sum_{i=0}^{k} i=\frac{k(k+1)}{2}

    Then let k=n-1
    I did simply subtitute it into the formula CB gave me. I don't have much experience with sequences and series. (I'm taking it next semester though.)
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] complexity theorie, deterministic turing-machines, time complexity
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: December 19th 2011, 06:44 AM
  2. Algorithm for determining if a graph is possible?
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: November 4th 2010, 01:12 PM
  3. complexity of this algorithm in my program
    Posted in the Math Software Forum
    Replies: 1
    Last Post: September 3rd 2009, 01:36 PM
  4. Complexity of Algorithm
    Posted in the Discrete Math Forum
    Replies: 9
    Last Post: June 21st 2008, 10:13 AM
  5. Complexity of Prime Algorithm
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: September 3rd 2006, 01:09 PM

Search Tags


/mathhelpforum @mathhelpforum