title: What constitutes 'array access' in the context of algorithms?
body: <p>Below is an LSD Radix sort implementation in Java from a textbook to sort an array of strings where each string contains exactly <code>W</code> characters.</p>
  
  <p>I want to count the number of array accesses during runtime. I've read that LSD sort is supposed to require <code>n * c</code> array accesses where <code>n</code> is the number of strings and <code>c</code> the amount of characters in each string. However, the algorithm below accesses more than one array several times. If I increment a counter at each of these I'll end up with a significant factor of <code>nc</code>.</p>
  
  <p>So what exactly constitutes 'array access' in the context of algorithms? Is there only one instance of array access that is considered more significant that I should count here, or is this example in fact an inefficient implementation that uses more array access than necessary? </p>
  
  <pre><code> public int lsdSort(String[] array, int W) {
    int access = 0;
    // Sort a[] on leading W characters.
    int N = array.length;
    String[] aux = new String[N];
    for (int d = W-1; d &gt;= 0; d--)
    { // Sort by key-indexed counting on dth char.
      int[] count = new int[R+1]; // Compute frequency counts.
      for (int i = 0; i &lt; N; i++) {
          count[array[i].charAt(d) + 1]++;
      }
      for (int r = 0; r &lt; R; r++) {
          // Transform counts to indices.
          count[r+1] += count[r];
      }
      for (int i = 0; i &lt; N; i++) {
          // Distribute.
          aux[count[array[i].charAt(d)]++] = array[i];
  
      }  
      for (int i = 0; i &lt; N; i++) // Copy back.
          array[i] = aux[i];
    }
  
    return access;
    }
  </code></pre>