Results 1 to 5 of 5
  1. #1
    ssjdx1 is offline Member
    Join Date
    Mar 2011
    Posts
    4
    Rep Power
    0

    Default 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 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.

  2. #2
    pbrockway2 is offline Moderator
    Join Date
    Feb 2009
    Location
    New Zealand
    Posts
    4,565
    Rep Power
    12

    Default

    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.

  3. #3
    ssjdx1 is offline Member
    Join Date
    Mar 2011
    Posts
    4
    Rep Power
    0

    Default

    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)

  4. #4
    pbrockway2 is offline Moderator
    Join Date
    Feb 2009
    Location
    New Zealand
    Posts
    4,565
    Rep Power
    12

    Default

    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).

  5. #5
    ssjdx1 is offline Member
    Join Date
    Mar 2011
    Posts
    4
    Rep Power
    0

    Default

    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

Similar Threads

  1. non primitive arrays
    By frosty in forum New To Java
    Replies: 2
    Last Post: 08-27-2010, 02:55 AM
  2. Primitive data type and class
    By Roselicious in forum New To Java
    Replies: 3
    Last Post: 04-19-2010, 03:27 PM
  3. JNI accessing non primitive data type
    By H_P in forum Advanced Java
    Replies: 1
    Last Post: 04-14-2010, 05:43 AM
  4. primitive Data types
    By Manfizy in forum New To Java
    Replies: 2
    Last Post: 07-07-2009, 08:29 PM
  5. Primitive data types of Java
    By Java Tip in forum Java Tip
    Replies: 0
    Last Post: 03-28-2008, 07:29 PM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •