Frequency Count in C

Dev Shed Forums Sponsor:

January 30th, 2013, 11:55 PM

kathyrollo

Contributing User

Join Date: Dec 2012

Location: Metro Manila, Philippines

Posts: 45

Time spent in forums: 18 h 57 m 8 sec
Reputation Power: 4

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.

February 20th, 2013, 05:39 PM

kathyrollo

Contributing User

Join Date: Dec 2012

Location: Metro Manila, Philippines

Posts: 45

Time spent in forums: 18 h 57 m 8 sec
Reputation Power: 4

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

February 21st, 2013, 12:09 AM

salem

Contributed User

Join Date: Jun 2005

Posts: 3,839

Folding Points: 153 Folding Title: Novice Folder

Time spent in forums: 2 Months 3 Weeks 2 Days 18 h 45 m 47 sec
Reputation Power: 1774

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

February 21st, 2013, 06:18 PM

kathyrollo

Contributing User

Join Date: Dec 2012

Location: Metro Manila, Philippines

Posts: 45

Time spent in forums: 18 h 57 m 8 sec
Reputation Power: 4

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!

February 23rd, 2013, 02:04 AM

clifford

Contributing User

Join Date: Aug 2003

Location: UK

Posts: 4,808

Time spent in forums: 1 Month 2 Days 17 h 42 m 14 sec
Reputation Power: 1800

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/Comput...ical_operations

Last edited by clifford : February 23rd, 2013 at 02:07 AM.

February 23rd, 2013, 08:09 AM

kathyrollo

Contributing User

Join Date: Dec 2012

Location: Metro Manila, Philippines

Posts: 45

Time spent in forums: 18 h 57 m 8 sec
Reputation Power: 4

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.

Frequency Count in C

Developer Shed Advertisers and Affiliates