Aggregate method
- Algorithms course
- Expert
- Lesson 2/41
- 4 min
Sum total cost, divide by operations.
Aggregate method
The aggregate method computes total cost for n operations and divides by n to get amortized cost. For dynamic arrays total cost is O(3n); amortized is O(1).
This method is the simplest amortized analysis technique. Total cost of all operations is computed.
Append operation
The append method adds a new element to the array. Most of the time it is O(1); only when capacity is full it becomes O(n).
Still, amortized cost is O(1) because the costly copy happens rarely. The aggregate method proves this.
Practice append_dyn function
Write append_dyn(arr, item). Add item to arr, return the new array. Print [1, 2, 3] with print(append_dyn([1, 2], 3)).
Starter code
def append_dyn(arr, item):
# Add item to arraySample solution
def append_dyn(arr, item):
# Add item to array
arr.append(item)
return arr
print(append_dyn([1, 2], 3))Expected output
[1, 2, 3]
Questions and answers
Review the lesson questions together with their answers. To test yourself, solve the lesson interactively.
1 Average computation
amortized = total_cost ____ namortized = total_cost / nExplanation: / is right.
2 What is the complexity of append most of the time?
- O(n²)
- O(n)
- O(1) Correct answer
- O(log n)
Explanation: Append is O(1) most of the time.
3 Aggregate method: match the terms
| Term | Meaning |
|---|---|
append |
Add |
total |
Total |
amortized |
Average |
O(1) |
Constant |