Dynamic array example

Dynamic array doubles but amortized O(1).

Dynamic array simulation

Let's simulate the total cost of pushing n elements. Each push is a write operation; when capacity is full, a copy is also done.

This simulation shows the practical side of amortized analysis. Total cost turns out close to the theoretical upper bound.

Cost formula

Total cost for n elements: n writes + copy costs. Copies grow as 1+2+4+...+2^k; total stays below n. Result: O(3n) ≈ 2n.

This is the practical proof that amortized cost is O(1). Each push takes constant time on average.

Exercise total_cost function

Write total_cost(n). Simulate n pushes; each push is 1 write, with extra copy when full. Return total cost. Print 7 with print(total_cost(4)).

Show example solution

def total_cost(n):
    # Compute total cost for n pushes
    cost = 0
    capacity = 1
    size = 0
    for i in range(n):
        if size == capacity:
            cost += size
            capacity *= 2
        cost += 1
        size += 1
    return cost
print(total_cost(4))

Test yourself

Dynamic array example: match the terms

write

1
copy

size
capacity

Double
size

Current
What does total_cost(4) return?
- 4
- 6
- 8
- 7
Show answer

7 — 1+2+3+1=7 (1st push 1, 2nd push 2, 3rd push 3, 4th push 1).
Capacity update
```
capacity ____ 2
```
Show answer
```
capacity *= 2
```

Next lesson: Summary - Amortized

We Are Enhancing Your Experience

Cookie Preferences

Strictly Necessary Cookies

Analytical Cookies