The complexity of fetching a value from an array is $$O(1)$$ because arrays allow direct access to their elements using an index. This is due to the way arrays are structured in memory.
Explanation
Memory Layout: Arrays are stored in contiguous memory locations. This means that if you know the starting address of the array (let's call it base_address), you can calculate the address of any element in the array using its index.
Index Calculation: The address of the $$i$$-th element in an array can be calculated using the formula:
$$
\text{address}(i) = \text{base_address} + i \times \text{size_of_element}
$$
Here, size_of_element is the size of each element in the array (e.g., 4 bytes for an integer in many systems).
Constant Time Access: Since the calculation of the address of an element involves only a few arithmetic operations (addition and multiplication), it takes constant time, regardless of the size of the array. This is why accessing an element by its index is $$O(1)$$.
Misconceptions
No Need to Traverse: Unlike searching for a value in an array, which may require checking each element (resulting in $$O(n)$$ complexity in the worst case), fetching...
