Counting Primitive Operators

[ssjdx1]

Hey, I was just trying to figure out how to count the primitive operations on pseudo code here is the code :-

Algorithm 1. ArrayMax(Arr)
Input: A 1-D numerical array Arr of size n
1) Let CurrentMax = a0
2) For i = 1 to n-1
3) If ai > CurrentMax Then CurrentMax = ai
4) End For
Output: CurrentMax



From my understanding :-
Line 1: one read and one write = 2
Line 2: a total of n-1 writes (changing i from 1 to n-1) = n-1

I am stuck on calculating line 3 because its within the loop any help would be much apprechated, thanks.

[pbrockway2]

I'm not sure exactly what counts as a "primitive operation", but line (3) occurs n-1 times. That means there are n-1 comparisons. I would imagine the comparisons count as operations, but possibly the array access (to get ai) doesn't. Anyway: whatever primitive operations you are associating with ai>CurrentMax you get n-1 of them.

The assignment part of line (3) is a bit tricky ... because it doesn't always happen! Basically it happens every time an element occurs to the right of some larger element. This may always be the case (99,98,97...) or it may never be the case (1,2,3...) or if the data is generated randomly then it would be expected to happen (n-1)/2 times (*). So you have to either assume some sort of input or describe the number of operations statistically.

(*) I think - but I've only had one coffee this am. I'm thinking mirrors.

[ssjdx1]

Thanks for that pbrockway2 with line 3 we usally assume the worst possible case which is when "Then CurrentMax = ai" will always occur im guessing that

If ai > CurrentMax Then CurrentMax = ai

CurrentMax = ai would be a read and write to thats 2 operations
the ai > CurrentMax contains 1 operator and 2 reads being of ai and CurrentMax
so that would be 5 operations however wouldnt the increment of i be an operation as well ?

Currently i'd assume line 3 to be 5(n-1)

[pbrockway2]

worst case is good (because it's easy - my estimate of the random case was garbage.)

When you increment you count 1 write, but don't you also have an increment? In code it would look like "i += 1" You are counting that as one operation: but aren't you doing some arithmetic and writing the result? (let alone reading the existing value of i).

[ssjdx1]

Im guessing with increment its just i = i + 1 so its 2 reads for 2 variables and one operator +
However the fact that we times the sum of the operators by (n-1) might mean its not necessery to count the increment im just assuming that though