# Array accesses and basic operations

I was looking through some lecture slides on algorithm analysis and found that in general an array access counted as a basic operation, but it did not seem to count as one when accessing the first element (e.g. A[i] is a basic operation but A[0] isn't). Does only accessing the first element count as a basic operation, and if it doesn't, does accessing an array by a predefined index (e.g. A[5]) count as one, and why is this the case?

• In regards to the lecture notes, I would imagine they mean A[5] takes 1 basic operation because it's essentially getting the memory address of A the adding 5 memory units (depending on what A contains). The addition would be the basic operation, whereas A[0] requires no addition to A. Usually the compiler will optimize these scenarios and, as David said, they're both essentially one step.
– ryan
May 15, 2017 at 18:56

It usually doesn't matter, since we're usually only interested in the order of growth of the number of steps. As long as we both agree that evaluating A[i] is a constant number of steps, independent of i, it doesn't actually matter what that constant is and we don't need to agree that it's the same constant. We'll both agree that the algorithm is, say, $\Theta(n^2)$, even if I think the running time is $45n^2 + 16n + 18$ and you think it's $68n^2+25n+21$. (And, in reality, neither of us is likely to be able to evaluate the running time to that level of precision.
So, it's usually fine to say that A[0] is a single step, as is A[5] (any sane compiler would compute "five cells beyond A[0]" at compile-time anyway) and A[i] where i is some variable. It won't make any difference to most analyses if you say that A[5] and A[i] are two operations due to having to compute the offset.
In some models of computation, things might be a bit more complicated because, if i is an arbitrary integer, it might not be sensible to assume that you can manipulate it in a constant number of steps. For example, on a standard Turing machine, you need to read $\log\texttt{i}$ tape cells just to know what i is. But that doesn't look much like what a real computer does.