What is an array and what are the complexities of its operations?

Question

Accepted Answer

An **array** is a contiguous block of memory holding elements of the same type, indexed from `0`. Because elements sit next to each other, the address of element `i` is computed directly as `base + i * elementSize`, giving **O(1) random access**.

## Memory layout

```text
index:    0     1     2     3     4
        +-----+-----+-----+-----+-----+
arr =   | 10  | 20  | 30  | 40  | 50  |
        +-----+-----+-----+-----+-----+
address: base  +4    +8    +12   +16   (4-byte ints)
```

## Example

```python
arr = [10, 20, 30, 40, 50]
x = arr[3]            # O(1) — direct index math
arr.append(60)        # amortized O(1) (dynamic array)
arr.insert(0, 5)      # O(n) — shift every element right
arr.pop(0)            # O(n) — shift every element left
```

## Complexity

| Operation | Time |
|---|---|
| Access by index | O(1) |
| Search (unsorted) | O(n) |
| Append (dynamic) | O(1) amortized |
| Insert/delete at front/middle | O(n) |

## Trade-offs

- **Strengths:** fast indexing, cache-friendly (data is contiguous), low memory overhead.
- **Weaknesses:** inserting/removing in the middle is O(n); fixed-size arrays require copying to grow.

## Why it matters

Arrays are the foundation under most other structures — strings, hash tables, heaps, and dynamic lists all build on them.

Their cache locality often makes a "slower" Big-O array beat a "faster" pointer-based structure in real benchmarks.

Operation	Time
Access by index	O(1)
Search (unsorted)	O(n)
Append (dynamic)	O(1) amortized
Insert/delete at front/middle	O(n)