Results 1 to 7 of 7

Math Help - Number of time Statement Executed

  1. #1
    Member
    Joined
    May 2006
    Posts
    148
    Thanks
    1

    Number of time Statement Executed

    From the following "pseudocodes", I have to determine how many times each statement

    x <-- x + 1 is executed and explain why, from the following options:

    O(1), O(log(n)), O(n), O(n*log(n)), O(n^2), O(n^3), O(2^n), or O(n!)

    The pseudocode is the following (I don't recall how to do the indentations, but I think its just the "code" thing).

    Code:
    a.) 
    
    for i <-- 1 to n
         for j <-- 1 to n
              for k <-- 1 to i
                   x <-- x + 1
              next k
         next j
    next i
    Code:
    b.)
    
    i <-- n
    while i >= 1
         for j <-- 1 to n
              x <-- x + 1
         next j
         i <-- [i/2] (square brackets without horizontal line at "top")
    end while
    Code:
    c.)
    
    i <-- 2
    while i < n
         i <-- i^2
         x <-- x + 1
    end while
    Code:
    d.)
    
    i <-- n
    while i >= 1
         for j <-- 1 to i
              x <-- x + 1
         next j
         i <-- [i/3] (square brackets without horizontal line at "top")
    end while
    *EDIT*

    Yay, [code] worked.
    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 fifthrapiers View Post
    From the following "pseudocodes", I have to determine how many times each statement

    x <-- x + 1 is executed and explain why, from the following options:

    O(1), O(log(n)), O(n), O(n*log(n)), O(n^2), O(n^3), O(2^n), or O(n!)

    The pseudocode is the following (I don't recall how to do the indentations, but I think its just the "code" thing).

    Code:
    a.) 
     
    for i <-- 1 to n
         for j <-- 1 to n
              for k <-- 1 to i
                   x <-- x + 1
              next k
         next j
    next i
    First check that the limits on the loops are what you intend.

    1. The innermost loop has i assignments.

    2. The next loop performs the inner loop n times, so with the inner loop
    has n.i assgnments.

    3. The outermost loop is performed for i=1..n, so the operations count
    is:

    <br />
\sum_{i=1}^n n\cdot i = n \sum_{i=1}^n i = n\ n(n+1)/2 = O(n^3) <br />
    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 fifthrapiers View Post
    From the following "pseudocodes", I have to determine how many times each statement

    x <-- x + 1 is executed and explain why, from the following options:

    O(1), O(log(n)), O(n), O(n*log(n)), O(n^2), O(n^3), O(2^n), or O(n!)

    The pseudocode is the following (I don't recall how to do the indentations, but I think its just the "code" thing).
    Code:
    b.)
     
    i <-- n
    while i >= 1
         for j <-- 1 to n
              x <-- x + 1
         next j
         i <-- [i/2] // [.] floor function
    end while
    1. The innermost loop has 1 assignment which is executed n times.

    2. The outer loop is executed \lfloor \log_2(n) \rfloor times

    3. Hence the total assignment count is:

    n\ \lfloor \log_2(n) \rfloor=O(n \log(n))
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member
    Joined
    May 2006
    Posts
    148
    Thanks
    1
    Let me see if I can do c and d now.

    For c:

    1. The innermost loop has i assignments.

    2. While x is less than n, there is 1 assignment.

    Therefore, n*n = n^2 = O(n^2)

    for d: This looks a lot like b.

    1. The outer loop is executed log(n) times.

    I think this one is similar to b, without the n scalar, so:

    O(log(n)).
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by fifthrapiers View Post
    Let me see if I can do c and d now.

    For c:

    1. The innermost loop has i assignments.

    2. While x is less than n, there is 1 assignment.

    Therefore, n*n = n^2 = O(n^2)
    Code:
    c.)
    i <-- 2 while i < n i <-- i^2 x <-- x + 1 end while
    (I will assume that the while statement should be "while i<=n" as this
    seems more natural to me than "while i<n", the changes needed if the latter
    really is intended should be easy enough to make)

    The loop has 1 assignment of the form x<--x+1, but how many trips
    around this loop are there?

    If n=2 or 3, then there is 1 trip, as i<--4 in the first trip and so
    i is now >n and so no further trips will be made.

    If n=4, 5, 6, 7, then there are two trips i<--8 after the second trip
    and so is now greater than n so there will be no further trips.

    In general if n=2^k, 2^k+1, .. , 2^{k+1}-1 there will be \lfloor \log_2(n) \rfloor=k
    trips, which is O(\log(n)).

    RonL
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by fifthrapiers View Post
    for d: This looks a lot like b.

    1. The outer loop is executed log(n) times.

    I think this one is similar to b, without the n scalar, so:

    O(log(n)).
    Except in b the inner loop had a trip count independent of the outer loop
    count, here we have a decreasing trip count as the outer loop progresses.

    I think we have a total trip count:

    <br />
N \sim n+\lfloor n/3 \rfloor +\lfloor n/9 \rfloor + ... +\lfloor n/3^{\lfloor \log_3(n) \rfloor} \rfloor=O(n)<br />

    In this case I feel the need to actualy conduct an experiment to check this.
    The attachment shows the result of this, and as the plot shows an essentialy straight line
    I am reasonably happy that the result is OK.

    RonL
    Attached Thumbnails Attached Thumbnails Number of time Statement Executed-gash.jpg  
    Last edited by CaptainBlack; November 3rd 2006 at 12:00 AM.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Member
    Joined
    May 2006
    Posts
    148
    Thanks
    1
    Thanks a lot, CaptainBlack.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 1
    Last Post: December 19th 2011, 03:27 PM
  2. Replies: 3
    Last Post: December 6th 2010, 02:52 AM
  3. False statement about the existence of a number
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: March 13th 2010, 03:41 PM
  4. Replies: 1
    Last Post: September 17th 2009, 03:51 AM
  5. Posting 2nd time(1st time didnt get anyhelp)
    Posted in the Calculus Forum
    Replies: 1
    Last Post: April 21st 2008, 08:21 PM

Search Tags


/mathhelpforum @mathhelpforum