Array Access Complexity

Question

In Java supppose I need to access array1[index] many times in the code.

Even for extremely large arrays, can I assume each single array access takes constant time?
Can this differ between languages or underlying architecture?

Answer 1

Accessing an element in an array is constant time (it just calculates an address offset). This behavior is consistent for all the languages you listed. Although it should not be assumed for all languages, it will apply to most.

There are some complexities in terms of cache miss/hit, pipelines etc but essentially its constant time.

This is not the case though for List. Some List implementations give different performance characteristics for different operations.

To expand on the complexities:

The question was "will large arrays get slower access". The correct answer is "yes".

It will stay O(1) in terms of Order of the access, but the actual access could potentially take considerably longer. For example it will become slower if the size of the array causes you to get cache misses (so the data needs fetching from main memory to the processor's cache) and/or memory paging issues (so the data needs fetching from disk), although that is a property of any large data set not specifically of arrays.

For most cases the difference will not be worth worrying about. We are talking fairly heavy optimization before you start worrying about things like cache misses. However it is worth being aware of these things as this question illustrates:

Why is it faster to process a sorted array than an unsorted array?

A seemingly irrelevant detail (pre-sorting of an array) on code that on the face of it should always take the same time ran five times as fast because of the detail of the way a processor works.

Answer 2

For large values of array1 size N can I assume each single array access (array1[index]) takes constant time?

In Java, yes. Also in C, C++, and C#, barring OS-level memory paging issues that are presumably out of scope.

Does this access time depend on language( java vs C++) or the underlying architecture ?

It can, if the language in question calls things "arrays" that aren't really arrays in the usual "contiguous block of memory" sense. (JavaScript does that; its Array ([]) type is really a map; PHP uses the term "array" as shorthand for "associative array" [e.g., map].) So for a given environment/language, it's worth checking that the term isn't being misused or used loosely.