January 31st, 2013, 12:55 AM

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 ifstatement 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 ifstatements and the maximum count of 2, I would get 1 + 1 + 2 = 4.
If I add it to the count of the last forblock 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, 06:39 PM

I think I understand this now. I should only add the counts for the two ifstatements 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 ifelse body)

2x + 3 = TOTAL FREQUENCY COUNT
February 21st, 2013, 01:09 AM

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.
February 21st, 2013, 07:18 PM

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, 03:04 AM

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 03:07 AM.
February 23rd, 2013, 09:09 AM

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.