Aggregate method

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.

Exercise 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)).

Show example solution

def append_dyn(arr, item):
    # Add item to array
    arr.append(item)
    return arr
print(append_dyn([1, 2], 3))

Test yourself

Average computation

amortized = total_cost ____ n

Show answer

amortized = total_cost / n

What is the complexity of append most of the time?
- O(n²)
- O(n)
- O(1)
- O(log n)
Show answer

O(1) — Append is O(1) most of the time.
Aggregate method: match the terms

append

Add
total

Total
amortized

Average
O(1)

Constant

Next lesson: Dynamic array example

We Are Enhancing Your Experience

Cookie Preferences

Strictly Necessary Cookies

Analytical Cookies