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.
Add a comment
|
1 Answer
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.)
6 Comments
Hans
I see. Thank you very much. Another related questions: given the address how does the computer find the element the address refers to and does it all take roughly the same time regardless of the addresses? Perhaps this encroaches on the realm of hardware. I am just curious.
Aasmund Eldhuset
The calculation is typically performed in hardware (it is usually available as a machine instruction, which typically will be executed as a sequence of microcode instructions), but it is very simple: startAddress + index * elementSize. When doing calculations by hand, it takes longer the more digits there are, but in hardware, a memory address always takes up the same amount of space, no matter how many digits it contains (although there is an upper limit on the number of digits), so the calculation is constant-time.
Hans
I have understood how the address is calculated right after reading your answer. My followup question in my last comment concerns not with how or how fast the calculation is performed, but with given the address, perhaps from the calculation you mentioned, how and how fast the computer finds the element this address refers to. Is the time for accessing the value the address refers to an increase function of some kind of distance of the location of that "object" to the origin where the search starts? I am sure even if this is the case, the whole process is very fast. But I am curious.
Aasmund Eldhuset
The key points is that there is no search involved (the computer calculates exactly where to look), and that this is electronics (no physical objects have to move around except for electrons). The only time difference caused by distance will be the extra time required for electrons to travel, which will typically be sub-nanosecond and shorter than the CPU's clock cycles. Inside the CPU, things generally happen at the rate of clock cycles anyway, so the differences won't matter (if there are differences at all - the circuits are typically designed to have equal-length paths to all locations).
Aasmund Eldhuset
See Wikipedia; a full DRAM chip consists of multiple larger versions of the circuit in the illustration, and a mechanism for selecting which one to read/write.
|