What is amortized?
- Algorithms course
- Expert
- Lesson 1/41
- 4 min
Average cost over a sequence of operations.
What is amortized?
Amortized analysis examines the average cost over a sequence of operations. Even if one operation is costly, the whole sequence may be cheap.
In a dynamic array, most appends are O(1), but when capacity is full an O(n) copy is needed. The average (amortized) cost is O(1).
Dynamic array
A dynamic array keeps appending to a fixed-capacity array; when full, it copies to a new array twice as large. We will ask the student to write a simple function showing this behavior.
A function returning an empty array forms the basis of the next steps.
Practice init_array function
Write init_array(). Return an empty array. Print it with print(init_array()).
Starter code
def init_array():
# Return empty arraySample solution
def init_array():
# Return empty array
return []
print(init_array())Expected output
[]
Questions and answers
Review the lesson questions together with their answers. To test yourself, solve the lesson interactively.
1 What happens when capacity is full in a dynamic array?
- Array is deleted
- Capacity doubles Correct answer
- Error is raised
- Element is dropped
Explanation: Capacity doubles and elements are copied.
2 Initial array
arr = ____arr = []Explanation: [] is right.
3 What is amortized: match the terms
| Term | Meaning |
|---|---|
amortized |
Average |
dynamic array |
Dynamic array |
doubling |
Double |
copy |
Copy |