Dynamic array example
- Algorithms course
- Expert
- Lesson 3/41
- 4 min
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.
Practice 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)).
Starter code
def total_cost(n):
# Compute total cost for n pushesSample 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))Expected output
7
Questions and answers
Review the lesson questions together with their answers. To test yourself, solve the lesson interactively.
1 Dynamic array example: match the terms
| Term | Meaning |
|---|---|
write |
1 |
copy |
size |
capacity |
Double |
size |
Current |
2 What does total_cost(4) return?
- 4
- 6
- 8
- 7 Correct answer
Explanation: 1+2+3+1=7 (1st push 1, 2nd push 2, 3rd push 3, 4th push 1).
3 Capacity update
capacity ____ 2capacity *= 2Explanation: *= is right.