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?

Solution 1

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.

Solution 2

Array lookup is always O(1). It does not depend on the size of the array. The basic idea about arrays is that it contains objects/references with fixed size so you can just do size * index to have the position of the object you are looking for.

So it is not like a LinkedList (which is O(n) nor a HashMap which is O(1) amortized.

I think this is the case in most languages. An exception might be javascript so make sure you check the documentation for the language you are using.

Solution 3

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.

Comments

[Bernhard Barker]

The array size certainly plays a role when considering that larger arrays may not fit on a memory page.

[Tim B]

It isn't the same in every language - one of the other answers mentions javascript for example.

[Adam Arold]

That's a memory paging issue not a language issue.

[Tim B]

But memory paging will change the access time.

[Adam Arold]

I think that you can say that in that corner case the access time is amortized O(1).

[Tim B]

The question was "will large arrays get slower access". The correct answer is "yes", O(1) is talking about the Order of the access, not about how long the access actually takes. It will be slower if the size of the array causes you to get cache misses and/or memory paging issues, although that is a property of any large data set not specifically of arrays.

[Tim B]

Having said that for most cases the difference will not be worth worrying about. Still its better to have all the details on an answer.