CODEWITHSUNDEEP
arraysvectortime-complexity
Hans
Hans

Reputation: 1379

The Complexity of Locating an Array Element

This is an extremely simple question I nevertheless would like to know the answer to. How does the complexity of locating the n'th element in a vector (an array) compared to that of comparing a natural number with a list of natural number of size n? I suppose they are both O(n) but with significantly different coefficients.

Upvotes: 0

Views: 36

Answers (1)

Aasmund Eldhuset
Aasmund Eldhuset

Reputation: 37950

No; array lookup is constant-time.

The reason for this is that computer memory is constructed so as to allow for constant-time access to any element as long as you have the address of it. An array is a contiguous sequence of elements, and therefore, you can compute the address of the desired element from the start address, the index, and the element size. (All elements must be of the same size; this might appear not to be the case in languages that allow you to put different kinds of elements into the same array, but in that situation, the elements of the array are actually references (memory addresses, in practice) to the objects.)

Upvotes: 1

Related Questions