Question: Does calling an element of an array by its index require parsing the entire array?
What do you mean by "parsing"?
Elements are consecutive in an array.
We know how much memory is reserved for each element.
We know the memory address of the first element.
We know, O(1), that element k is at address first + k * size.
Was that a 'yes' or a 'no'?
Elements are consecutive in an array.
We know how much memory is reserved for each element.
We know the memory address of the first element.
We know, O(1), that element k is at address first + k * size.
Was that a 'yes' or a 'no'?
I mean,
if I call for an element at index 5, does the computer have to go through the array consecutively, one element at at time, and check if the index at the current element equals 5 until an element's index equals 5?
if I call for an element at index 5, does the computer have to go through the array consecutively, one element at at time, and check if the index at the current element equals 5 until an element's index equals 5?
Last edited on
No. The computer finds the address of the element by doing some arithmetic. It stores the address of the first element, then the address of then Nth element is (address of first) + N * sizeof(one element).
If the index is a constant, like arr[4], the compiler can do the arithmetic at compile time. Pretty cool, huh?
If the index is a constant, like arr[4], the compiler can do the arithmetic at compile time. Pretty cool, huh?
Topic archived. No new replies allowed.