Dynamic Arrays

Core idea

A dynamic array is an array-like data structure that can automatically grow when its current storage becomes full.

Python’s list behaves like a dynamic array.

Size vs Capacity

This distinction is fundamental.

Size = number of elements currently stored.
Capacity = total number of elements the allocated storage can currently hold.

Example:

[10, 20, 30, __, __]

size     = 3
capacity = 5

Therefore:

size <= capacity

Append when capacity is available

Suppose:

size     = 3
capacity = 5

[10, 20, 30, __, __]

Appending 40 simply uses the next free slot:

[10, 20, 30, 40, __]

No elements need to move.

append → O(1)

What happens when capacity is full?

Suppose:

size     = 5
capacity = 5

[10, 20, 30, 40, 50]

Appending another element requires more storage.

Conceptually:

Old capacity = 5
        ↓
Allocate larger array
        ↓
Copy existing elements
        ↓
Add new element

If the new capacity is larger by a multiplicative growth factor, such as roughly 2×:

Old:
[10, 20, 30, 40, 50]

New:
[10, 20, 30, 40, 50, __, __, __, __, __]

Copying the existing n elements costs:

O(n)

Therefore:

Append causing resize → O(n) worst case

Amortized O(1)

This is the most important concept in dynamic arrays.

A single append can be expensive:

Normal append          → O(1)
Append causing resize  → O(n)

But resizing does not happen on every append.

If capacity grows geometrically:

1 → 2 → 4 → 8 → 16 → 32 → ...

the total amount of copying over many appends is linear.

For n appends, the total copying is:

1 + 2 + 4 + 8 + ... < 2n

Therefore:

Total cost of n appends = O(n)

Amortized cost per append:

O(n) / n = O(1)

Important

Amortized O(1) does NOT mean every append is O(1).

It means that across a long sequence of appends, the average cost per append is O(1).

Example

arr = []

for i in range(n):
    arr.append(i)

There are n appends.

Although some individual appends trigger resizing, the total work is O(n).

Therefore:

Overall time → O(n)
Amortized append → O(1)

Insertions

Consider:

arr.insert(0, 100)

For:

[10, 20, 30, 40]

the result must be:

[100, 10, 20, 30, 40]

The existing elements have to shift right.

Therefore:

Insert at beginning → O(n)
Insert in middle    → O(n)

Even if the dynamic array has spare capacity, shifting elements still costs O(n).

Deletions

Deleting from the beginning or middle also requires shifting:

[10, 20, 30, 40, 50]

delete 30

[10, 20, 40, 50]

Therefore:

Delete beginning → O(n)
Delete middle    → O(n)
Delete end       → O(1)

Dynamic Array Complexity

Operation	Complexity
Access `arr[i]`	O(1)
Update `arr[i]`	O(1)
Search	O(n)
Append	O(1) amortized
Append causing resize	O(n) worst case
Insert beginning	O(n)
Insert middle	O(n)
Delete beginning	O(n)
Delete middle	O(n)
Delete end	O(1)

Why grow geometrically?

If capacity increased by only one:

1 → 2 → 3 → 4 → 5 → 6 → ...

the array would need to resize very frequently.

Instead, dynamic arrays increase capacity by a multiplicative growth factor:

1 → 2 → 4 → 8 → 16 → 32 → ...

This makes resizing sufficiently infrequent to provide amortized O(1) append performance.

The exact growth policy depends on the implementation.

Python

Python’s list is a dynamic array:

nums = []

nums.append(10)
nums.append(20)
nums.append(30)

Conceptually, Python manages the underlying storage and resizing for you.

For interview analysis:

list.append(x)
→ O(1) amortized
→ O(n) worst case when resizing occurs

Static vs Dynamic Array

Feature	Static Array	Dynamic Array
Size	Fixed	Can grow
Contiguous storage	Yes	Yes
Index access	O(1)	O(1)
Search	O(n)	O(n)
Append	O(1) if capacity exists	O(1) amortized
Resize	Manual/new allocation	Automatic

Mental model

Dynamic Array
      ↓
size + capacity
      ↓
Capacity available?
   ↙          ↘
 yes           no
  ↓             ↓
append        resize
O(1)          copy elements
              O(n)

Across many appends:

n appends
    ↓
O(n) total work
    ↓
O(1) amortized per append

Interview answers to memorize

Why is array access O(1)?

Arrays use contiguous memory, so the address of an indexed element can be calculated directly.

Why can dynamic-array append be O(n)?

When capacity is full, a larger array must be allocated and the existing elements copied.

Why is append amortized O(1)?

Resizing happens only occasionally, and geometric capacity growth makes the total cost of resizing across many appends O(n), giving O(1) amortized cost per append.

Why is insertion at the beginning O(n)?

Existing elements must be shifted to make room for the new element.

Quick Revision

Dynamic Array:
- Has size and capacity
- Size = elements currently stored
- Capacity = allocated slots
- Access → O(1)
- Update → O(1)
- Search → O(n)
- Append → O(1) amortized
- Resize-triggering append → O(n) worst case
- Insert beginning/middle → O(n)
- Delete beginning/middle → O(n)
- Delete end → O(1)

Key concept:
Amortized O(1) ≠ every operation is O(1).

It means:
Total cost over many operations / number of operations = O(1)