I have read that to look up the value at index n of an array, the computer will calculate (array start location) + (n * (data type size)) to find the location in memory of the value. Would this not take more than O(1) time because multiplication takes more than O(1) time?
1 Answers
Theoretically, you are right in your thinking. Addition and multiplication can never be done in constant-time with respect to the input numbers.
The reason why indexed access is considered O(1) is that in practice, you work on a computer with limited RAM memory and an even more limited (logarithmic) address space. Indeed, these addresses usually fit in a single word on the hardware. They are considered constant-space in the context of random-access memory. Thus, also simple arithmetic with these addresses are considered to run in constant-time. So anything you would do in practice on your machine, any algorithm you program, random-access can be assumed to be constant-time.
Basically, you compute c + d * e where all values are bounded by a constant.
But yes, if you consider a theoretical machine with infinite memory, then doing operations on your addresses will not be constant-time, even with random access.
Related