Array accesses and basic operations

Question

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?

Answer 1

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.