How come the complexity of fetching a value from an array by it's index is O(1)?I thought the algorithm has to go through all the indexes, find the correct index, and then know what value to return. So that means the complexity is O(n/2) on average.Why is it actually O(1)?
Why is the complexity of fetching a value from an array be O(1)?
data structures;array;big o
The key to understanding why array access is O(1) is understanding that they have a known length. In a language like C, we can guarantee this by allocating a sequential block of memory. Since it's sequential in memory, we can use pointer arithmetic for direct addressing and thus direct access. An array object would follow a similar principle with its internal organization though the implementation might be more complex. Since all we are doing is some addition, an operation that takes O(1) time, we have an operation that over all takes O(1) time. This addition is also why in C and C++ at least, all items in an array need to be the same type. They all are required to occupy the same number of bytes for this pointer arithmetic to work.Contrast this to a singly linked list where we have a defined beginning of the list and then we add on to that list by having a pointer or reference address point to the next node in the list. Each node contains two things, a pointer to the next node in the list and a data item. Since you can't go back, each time you want an item from the list, even if you know exactly where it is, you need to traverse the whole list up to that item. Thus, we wind up with O(n/2) for average case access and O(n) for worst case. We can mitigate this some by doing a doubly linked list with a tail pointer as well as a head pointer but we still are limited to a form of sequential, rather than truly random, access. We set the last pointer to null to essentially tell the computer the same thing we are telling it when we give in the size of an array.