Menu
According to Wikipedia, accessing any single element in an array takes constant time as only one operation has to be performed to locate it.
To me, what happens behind the scenes probably looks something like this:
a) The search is done linearly (e.g. I want to access element 5. I begin the search at index 0, if it's not equal to 5, I go to index 1 etc.) This is O(n) -- where n is the length of the array
b) If the array is stored as a B-tree, this would give O(log n)
I see no other approach.
Can someone please explain why and how this is done in O(1)?
507
Why the complexity of fetching value is O(1)? As Arrays are allocated contiguously in memory, Fetching a value via an index of the array is an arithmetic operation. All arithmetic operations are done in constant time i.e., O(1).
In case of array the memory location is calculated by using base pointer, index of element and size of element. This involves multiplication and addition operation which takes constant time to execute. Hence element access inside array takes constant time.
We all know that indexing into an array takes only O(1) time, while searching for a number in a sorted array takes O(n) time with linear search, and O(log n) time with binary search.
accessing a list l at index n l[n] is O(1) because it is not implemented as a Vanilla linked list where one needs to jump between pointers (value, next-->) n times to reach cell index n.
An array starts at a specific memory address start. Each element occupies the same amount of bytes element_size. The array elements are located one after another in the memory from the start address on. So you can calculate the memory address of the element i with start + i * element_size. This computation is independent of the array size and is therefor O(1).
139
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
