Big-O of Getting Element at Specific Index in an Array

Last updated on 6 Dec, 2022

Here is an array:

const arr = [2, 5, 1, 9, 3];

Array are stored in contigous memory locations. So 2, 5, 1, 9, 3 are stored in contigous memory locations. Let us assume arr stores only 8 bit integers. So each element takes 1 byte of memory.

arr[1]; // 5
arr[4]; // 3

When program needs to take the value of any element, compiler can jump to the index location by calculating the memory address of the element. Since, the length of each element in an array is same, computer just needs to multiply offset with element size.

Since the time taken is always a constant irrespective of the position, Big-O of getting an element from an array is O(1).

--- ○ ---
Joby Joseph
Web Architect