Results 1 to 5 of 5
Thread: Counting Primitive Operators
 04232011, 11:44 PM #1Member
 Join Date
 Mar 2011
 Posts
 4
 Rep Power
 0
Counting Primitive Operators
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 1D numerical array Arr of size n
1) Let CurrentMax = a0
2) For i = 1 to n1
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 n1 writes (changing i from 1 to n1) = n1
I am stuck on calculating line 3 because its within the loop any help would be much apprechated, thanks.
 04242011, 12:06 AM #2Moderator
 Join Date
 Feb 2009
 Location
 New Zealand
 Posts
 4,614
 Rep Power
 12
I'm not sure exactly what counts as a "primitive operation", but line (3) occurs n1 times. That means there are n1 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 n1 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 (n1)/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.
 04242011, 12:16 AM #3Member
 Join Date
 Mar 2011
 Posts
 4
 Rep Power
 0
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(n1)
 04242011, 12:43 AM #4Moderator
 Join Date
 Feb 2009
 Location
 New Zealand
 Posts
 4,614
 Rep Power
 12
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).
 04242011, 02:00 AM #5Member
 Join Date
 Mar 2011
 Posts
 4
 Rep Power
 0
Similar Threads

non primitive arrays
By frosty in forum New To JavaReplies: 2Last Post: 08272010, 02:55 AM 
Primitive data type and class
By Roselicious in forum New To JavaReplies: 3Last Post: 04192010, 03:27 PM 
JNI accessing non primitive data type
By H_P in forum Advanced JavaReplies: 1Last Post: 04142010, 05:43 AM 
primitive Data types
By Manfizy in forum New To JavaReplies: 2Last Post: 07072009, 08:29 PM 
Primitive data types of Java
By Java Tip in forum Java TipReplies: 0Last Post: 03282008, 08:29 PM
Bookmarks