#1
  1. Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Dec 2012
    Location
    Manila, Philippines
    Posts
    64
    Rep Power
    5

    Question Frequency Count in C


    Hi guys,

    Our lesson is about frequency count or calculating the number of steps needed by an algorithm to finish.

    Below is an example provided in our lecture notes:
    Code:
    if x < 1
    y ← 10;
    
    else if x < 2
    { y ← 20; z ← 30;
    }
    
    else
    { for i ← 1 to x
    print(i);
    }
    Total = 2x + 3


    I understand this block yields a total of 2x + 1:
    Code:
    else
    { for i ← 1 to x     x - 1 + 2 = x + 1
    print(i);            x - 1 + 1 = x
    }                               -------
                                     2x + 1
    But I'm quite lost about this block:
    Code:
    if x < 1                 1
    y ← 10;               1
    
    else if x < 2            1
    { y ← 20; z ← 30;     2
    }
    I understand that each if-statement would always entail a count of 1 and it must be added to the maximum count of statements which is in this example, 2.

    If I add both the if-statements and the maximum count of 2, I would get 1 + 1 + 2 = 4.

    If I add it to the count of the last for-block to obtain the total count, I would get 2x + 1 + 4 = 2x + 5.

    As you can see, I'm not getting the right answer. Help would be very much appreciated.

    Thank you.
  2. #2
  3. Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Dec 2012
    Location
    Manila, Philippines
    Posts
    64
    Rep Power
    5
    I think I understand this now. I should only add the counts for the two if-statements which is 1 + 1 = 2 and the maximum count for the body which is 2x + 1 (since it is greater than 1 or 2). Therefore:
    Code:
            1 (count of if x < 1)
            1 (count of if x < 2)
     + 2x + 1 (max count of if-else body)
    ----------
       2x + 3 = TOTAL FREQUENCY COUNT
  4. #3
  5. Contributed User
    Devshed Specialist (4000 - 4499 posts)

    Join Date
    Jun 2005
    Posts
    4,392
    Rep Power
    1871
    Are you just counting statements, in which case your approach seems fine?

    Or are you looking at complexity, in which case the answer is just x.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper
  6. #4
  7. Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Dec 2012
    Location
    Manila, Philippines
    Posts
    64
    Rep Power
    5
    Hi Salem,

    In this lesson, we are counting statements. I believe we haven't touched complexity yet.

    (1) How is complexity different from counting statements and (2) would you kindly illustrate how it became x for this particular problem?

    Thank you!
  8. #5
  9. Contributing User

    Join Date
    Aug 2003
    Location
    UK
    Posts
    5,113
    Rep Power
    1803
    Salem did well to even have an idea what your question was about! It was neither clear or in fact "on topic" with this forum which is about C and related language programming rather than computer science.

    Regarding complexity. this might be germane: http://en.wikipedia.org/wiki/Computa...cal_operations
    Last edited by clifford; February 23rd, 2013 at 02:07 AM.
  10. #6
  11. Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Dec 2012
    Location
    Manila, Philippines
    Posts
    64
    Rep Power
    5
    Indeed. I figured replies might not come as easy for this post. I posted in the C board because our professor was giving examples in C, I wasn't sure if the formula for statement count would be different in other languages.

IMN logo majestic logo threadwatch logo seochat tools logo