When I started working in web development, I had no idea why array[index] is n(1) because I was primarily working with high-level languages, and the mystery carried on with me until I started working with low-level language Rust.
To answer why it's n(1), we must first understand what a pointer is: an object that stores a memory address. Thus when we use a pointer, we are accessing a memory location rather than the underlying data.
As for the array data structure, an array is a collection of elements stored in a contiguous memory location; it fulfills an entire row of memory addresses with no spaces or gaps between elements.
Now that we have defined what a pointer and array are, it won't be a surprise when I say that when we instantiate an array, we create a pointer (The naming differs between languages)
let arr = [1,2,3,4,5]
Now that we know that arr is a pointer (with extra data like length, size), it's safe to say that arr is pointing to the memory address of the first element of the array. In other words, the memory address of arr and the memory address of arr[0] is the same.
Lastly, an example would make everything clear. Let's say that arr is in memory location 10, which means that the first element is also in memory location 10; now, assuming that Number in Javascript is 8 Bytes, the second element will be in location 18, and the third will be in 26.
arr[0] -> stored in memory location 10
arr[1] -> stored in memory location 18
arr[2] -> stored in memory location 26
And that is why array[index] is n(1) because all we need to get is the memory location of the first element + (Data size in bytes * index).
Top comments (0)