Results 1 to 3 of 3

Math Help - big O notation

  1. #1
    Member
    Joined
    Jul 2008
    Posts
    89

    big O notation

    I am working on this algorithm and I am supposed to select a notation for the number of times the statement x = x + 1 is executed in the algorithm:

    Code:
    for i = 1 to n
      for j = 1 to n
        for k = 1 to i
    
      x = x + 1
    if each integer 1 + 2 + ... n <= n + n + ... n = n * n * n = n^3 for all n >= 1.

    it follows that

    1 + 2 + ... n = O(n^3)


    My question here is did I explain myself correctly to get O(n^3)?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,527
    Thanks
    773
    No. For each i, the two inner loops take 1 + 2 + ... n (n terms) <= n + n + ... n (n terms) = n^2. However, the inner loops are run for each i from 1 to n.

    I assume that the body of the innermost loop consisted of x = x + 1. As it is, the indentation may suggest that the innermost loop is empty and the assignment is done in the outermost loop.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by emakarov View Post
    No. For each i, the two inner loops take 1 + 2 + ... n (n terms) <= n + n + ... n (n terms) = n^2. However, the inner loops are run for each i from 1 to n.
    It is desirable to actually sum 1+2+..+n rather than bound it this way so that we know that the smallest integer k such that we can write 1+2+ .. +n =O(n^k) is 2

    CB
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 1
    Last Post: March 10th 2011, 02:23 AM
  2. nCr notation
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: August 30th 2010, 10:51 AM
  3. Notation
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: June 4th 2010, 11:36 AM
  4. Replies: 1
    Last Post: August 26th 2009, 12:40 PM
  5. Notation
    Posted in the Advanced Statistics Forum
    Replies: 2
    Last Post: March 27th 2009, 08:26 PM

Search Tags


/mathhelpforum @mathhelpforum