What's the time complexity of indexing a numpy array directly

On the one hand

must be using a hash-table which will give a time complexity close to O(1). Is that right?

is not quite true. Numpy arrays are basically contiguous blocks of homogeneous memory, with some extra info on the side on dimensions and such. Therefore, the access is O(1), and just involves some trivial math to determine the position within the memory.

On the other hand

indexing must be pretty efficient.

is unfortunately not true at all. Asides from bounds checking (which arrays do), everything involving pure python is extremely inefficient (and accesses involve pure-python calls). Numpy array access is no exception. You should try to use vector operations whenever possible.


There is no hash table involved. Numpy arrays are arrays, just like the name implies, and the address is computed like this:

address of nArray[x, y] = base address + A * x + B * y