Counting array accesses

Question

I am trying to figure out how to determine the complexity(array accesses) of certain simple methods.

I'd like some confirmation if I'm doing this right. For example this method.

    int i = 0;  
    while(i < N){
        clone[i][j] = clone[++i][j];
        clone[i][j] = 0;
    }

Do the array accesses sum up to three here? One forclone[i][j] another for clone[++i][j] and lastly another one for clone[i][j]. Meaning this has ± 3N array accesses?

How about something like this:

if(clone[i][j] == value1 || clone[i][j] == value2)

Can I consider this to be one array access, or two?

Thanks in advance!

Answer 1

I'd count these as six array accesses.

You are accessing 2D arrays, and a statement like

clone[i][j] = 0;

could be written analogously as

int temp[] = clone[i];
temp[j] = 0;

You can also have a look at the bytecode: A a class like

class ArrayAcc
{
    static void foo()
    {
        int array[][] = new int[2][2];
        array[1][1] = 123;
    }

}

compiled and disassembled with

javap -c ArrayAcc.class

gives the following output:

....
static void foo();
Code:
   0: iconst_2
   1: iconst_2
   2: multianewarray #2,  2             // class "[[I"
   6: astore_0
   7: aload_0
   8: iconst_1
   9: aaload
  10: iconst_1
  11: bipush        123
  13: iastore
  14: return

The aaload instruction loads the reference to the "inner" array on the stack. The iastore instruction puts the value 123 into this "inner" array.

---

For the other part of the question,

if(clone[i][j] == value1 || clone[i][j] == value2)

Here it depends on whether the first condition is true or not. If the first condition is true, then the second one will not be evaluated. If you wrote

if(clone[i][j] == value1 | clone[i][j] == value2)

(with a single |) then you'd always check both conditions.