Summary - Amortized
- Algorithms course
- Expert
- Lesson 4/41
- 4 min
Print amortized cost in a mini task.
Summary - Amortized
In this group you learned amortized analysis and the dynamic array example. Dividing total cost by n gives amortized cost.
Now you will write a function that brings all pieces together. This summary unites the group's concepts in a single piece of code.
Practice amortized_average function
Write amortized_average(n). total_cost is given; return total_cost(n) // n. Print 1 with print(amortized_average(4)).
Starter code
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
def amortized_average(n):
# Compute amortized costSample 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
def amortized_average(n):
# Compute amortized cost
return total_cost(n) // n
print(amortized_average(4))Expected output
1
Questions and answers
Review the lesson questions together with their answers. To test yourself, solve the lesson interactively.
1 How is amortized cost found?
- Total cost / n Correct answer
- Total cost × n
- Total cost + n
- Total cost - n
Explanation: Amortized = total cost / n.
2 Amortized computation
Question
amortized = total_cost(n) ____ n
Answer
amortized = total_cost(n) / nExplanation: / is right.
3 Summary - Amortized: match the terms
| Term | Meaning |
|---|---|
init_array |
Empty array |
append_dyn |
Add |
total_cost |
Total |
amortized |
Average |