What is the time complexity of index access?
Short answer
Index access in a regular or dynamic array (Array, std::vector, ArrayList, Python list, JS Array) is O(1). In linked lists it is O(n). In trees/ropes/persistent vectors it is O(log n) (often O(logₖ n)).
Detailed explanation
"Index access" means the operation of getting an element at position i. Complexity depends on the internal layout of the data structure.
Why arrays give O(1)
- Contiguous memory: element i sits at address base + i * size, computed in constant time.
- Complexity does not depend on n (the number of elements), only on i and the element size.
- Bounds checking, cache hits, page faults are constant factors; they do not change the asymptotics.
Code examples
// C++: a static array and std::vector, indexing is O(1)
#include <vector>
#include <iostream>
int main(){
int a[5] = {10,20,30,40,50};
std::vector<int> v = {10,20,30,40,50};
std::cout << a[3] << " " << v[3] << "\n"; // the 4th element, O(1)
}# Python: list, a dynamic array, index access is O(1)
arr = [10, 20, 30, 40, 50]
print(arr[3]) # 40// JavaScript: Array, average case O(1) for dense arrays
const arr = [10, 20, 30, 40, 50];
console.log(arr[3]); // 40// Java: Array and ArrayList, index access is O(1)
import java.util.*;
class Main{
public static void main(String[] args){
int[] a = {10,20,30,40,50};
System.out.println(a[3]); // 40
List<Integer> list = new ArrayList<>(Arrays.asList(10,20,30,40,50));
System.out.println(list.get(3)); // 40
}
}When index access is not O(1)
| Structure | Complexity | Comment |
|---|---|---|
| Singly/doubly linked list | O(n) | You must walk i nodes from the head/tail. |
| Trees (B-tree, segment tree, Fenwick tree by index) | O(log n) | Traversal across tree levels. |
| Rope | O(log n) | The string is a tree of chunks; index lookup walks the tree. |
| Persistent vector (e.g. Clojure) | O(logₖ n), usually O(log₃₂ n) | A high-branching tree gives an almost constant depth. |
| Deque/LinkedList (Java) by index | O(n) | No direct random access. |
| JS sparse arrays | Amortized O(1), high constant | May be stored as a hash table/property entries, without a dense buffer. |
- Strings: accessing the i-th byte/code unit is usually O(1). But accessing the i-th grapheme cluster (a visible Unicode "character") may require a scan, up to O(n).
- Associative arrays/dictionaries are not indexed by position; there access is by key, usually amortized O(1), not by index.
Amortized versus worst case
Dynamic arrays sometimes reallocate memory as they grow; this affects insert/grow operations, but not reading by index: get(i) stays O(1) in the worst case. Insertions/deletions in the middle are O(n), but that is a different operation.
Summary
If the structure is a contiguous array (including a dynamic one), index access is O(1). Once the data is split into nodes or levels (lists, trees, ropes, persistent structures), complexity grows to O(n) or O(log n).
Short Answer
Interview readyA concise answer to help you respond confidently on this topic during an interview.