Amortized Time Complexity

What Is Amortized Time Complexity

The time complexity per operation, derived by evaluating the total cost across a sequence of operations and distributing that cost among each individual operation.

Example

This is explained using a dynamic array as an example.

Assumptions:

• A dynamic array with 0 elements and capacity 1 is created initially.
• Elements are appended one at a time, for a total of N appends.
• When capacity is exceeded, it is doubled.
• When expanding, a new array is allocated and all existing elements are copied into it.
• Writing and copying a single element takes O(1) time.
• Allocating a new array takes O(1) time.

Time complexity of each operation:

• Creating the initial array: O(1)
• Writing N elements: O(N)
• Allocating arrays for expansion (once per capacity overflow): O(log N)
• Copying existing elements during expansion (once per capacity overflow): O(N)

The total time complexity of all operations is: O(1) + O(N) + O(N) + O(log N) = O(N)

The total time complexity of all expansion operations across every capacity overflow is: O(N) + O(log N) = O(N)

The total time complexity of all operations is O(N). Dividing by the number of append operations N gives the amortized time complexity: O(N) / N = O(1).