What is amortized?

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.

Exercise init_array function

Write init_array(). Return an empty array. Print it with print(init_array()).

Show example solution

def init_array():
    # Return empty array
    return []
print(init_array())

Test yourself

What happens when capacity is full in a dynamic array?
- Array is deleted
- Capacity doubles
- Error is raised
- Element is dropped
Show answer

Capacity doubles — Capacity doubles and elements are copied.
Initial array
```
arr = ____
```
Show answer
```
arr = []
```
What is amortized: match the terms

amortized

Average
dynamic array

Dynamic array
doubling

Double
copy

Copy

Next lesson: Aggregate method

We Are Enhancing Your Experience

Cookie Preferences

Strictly Necessary Cookies

Analytical Cookies