# Amortized time complexity

**Amortized complexity analysis** is most commonly used with data structures,
which have state that persists between operations.
The basic idea is that an expensive operation can alter the state so that
the worst case cannot occur again for a long time, thus amortizing its cost.

Definition:Let T_{1}, T_{2}, …, T_{k}be the complexities of a sequence of operations on a data structuture. Theamortized complexityof a single operation in this sequence is (T_{1}+ T_{2}+ …+ T_{k}) / k.

## Example

Algorithmappend(arr, x):ifarr.size == arr.capacity arr.capacity ← 2 * arr.capacity resize arr arr[arr.size] ← x arr.size ← arr.size + 1

Let’s start by looking at the worst case:

The worst-case time complexity for appending an element to an array of lengthnusing this algorithm is Θ(n):

- if the array is full, the algorithm allocates a new array of length 2
n,- and then copies the elements from the old array into the new one.

Cleary, this result is overly pessimistic.
The following *n* append operations will be much cheaper:
each of them will run in constant time since the newly allocated array
has room for all of the new elements.

An amortized time analysis gives a better understanding of the algorithm:

Consider a sequence ofnappend operations, where we start with an array of length 1. A careful analysis shows that the total time of these operations is only Θ(n):Hence, the amortized time complexity for a single append operation is Θ(1).

- There will be a total of
nconstant-time assignment and increment operations.- The resizing will happen only at operation 1, 2, 4, …, 2
^{k}, for a total of 1 + 2 + 4 + …+ 2^{k}= 2·2^{k}- 1 constant-time element copy operations. Since 2^{k}≤n, this is at most 2n- 1.

## Comments