Suggest an edit

Improve this article

Refine the answer for “What is the time complexity of index access?”. Your changes go to moderation before they’re published.

Approval required

Content

What you’re changing

Title (EN)

Short answer (EN)

Shown above the full answer for quick recall.

Answer (EN)

## 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

```cpp
// 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
# Python: list, a dynamic array, index access is O(1)
arr = [10, 20, 30, 40, 50]
print(arr[3])  # 40
```

```javascript
// JavaScript: Array, average case O(1) for dense arrays
const arr = [10, 20, 30, 40, 50];
console.log(arr[3]); // 40
```

```java
// 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).

Markdown · drag & drop images · ⌘B / ⌘I shortcuts493 words

For the reviewer

Note to the moderator (optional)

Visible only to the moderator. Helps review go faster.