0
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – ryan May 15 '17 at 18:56
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks for the in-depth answer! I'll email the lecturer just to make sure what he wants for the exam, but that's a great answer when it comes to the real world. $\endgroup$ – Rob Murray May 16 '17 at 14:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.