Summary - Amortized

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.

Exercise amortized_average function

Write amortized_average(n). total_cost is given; return total_cost(n) // n. Print 1 with print(amortized_average(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
def amortized_average(n):
    # Compute amortized cost
    return total_cost(n) // n
print(amortized_average(4))

Test yourself

How is amortized cost found?
- Total cost / n
- Total cost × n
- Total cost + n
- Total cost - n
Show answer

Total cost / n — Amortized = total cost / n.

Amortized computation

amortized = total_cost(n) ____ n

Show answer

amortized = total_cost(n) / n

Summary - Amortized: match the terms

init_array

Empty array
append_dyn

Add
total_cost

Total
amortized

Average

Next lesson: P and NP

We Are Enhancing Your Experience

Cookie Preferences

Strictly Necessary Cookies

Analytical Cookies