Big 0

[Rawkhawk]

I need to figure out a running time function which provides a formula for the total number of operations (additions and assignments) performed on the variable sum.

(a) for(int i = 0; i < n+1; i++) sum = sum + 4;

Correct Answer:

f(n) = 2n + 1
Thus the big o is O(n)

I don't understand how the f(n) part was calculated.

Anyone know?

[Albatross]

Oh, yessss! I love computability theory! ^_^

Consider the number of times the loop runs. n + 1 times, right? Now, note that two operations per run of the loop were executed (i was first ++ed and sum was +=4ed), except for the first loop in which i is not ++ed at the very start.

Therefore, it's 2(n+1) - 1 which is 2n + 1.

Do you understand how they got it?

-Albatross

[Rawkhawk]

hmm. I think I understand that. I'm going to add on another one

for(int i = 0; i < 2*n; i++)
{
for(int j = 0; j < 2*n; j++)
{
sum = sum + 1;
}
}

So right here, the i++ and j++ add 2
and the for loops execute n times that's going to be n^2 + 2. And then the sum += 1 puts the 2 out front so it's 2(n*n + 2) -2???

(I know the answer so i probably got it right....but my explanation is still wrong.) >_<

[Albatross]

The outer loop runs 2n times. On completion it will have executed 2n - 1 operations, excluding the inner loop, and the inner loop is run 2n times, has 2n iterations, and has 2 operations per iteration save the first which has 1 operation. Can you rephrase this in your own words?

(I hope I'm not low on caffeine).

-Albatross

[Rawkhawk]

soooo.....>_< 2n -1 for both the outer and inner loops. seems like it would be (2n-1) * (2n-1) 4n^2 - 2n -2n + 1

4n^2 - 4n + 1 is definitly not right so...i guess i can't >_<