From charlesreid1

Notes

An operation takes "T(n) amortized" if k operations take  \leq k \cdot T(n) time

k inserts take theta(k) time, so this is O(1) amortized insert

Methods for amortized analysis:

Amortization of resizing:

Aggregate Method

The simplest way of thinking about amortization is using the aggregate method: to compute the amortized cost per operation, we sum up the time for k operations, and divide by k.

Amortized cost per operation = ( total cost of k operations ) / ( k )

The downside is, mixing different operations makes things more complicated.

More General Definition

The more general way of talking about an amortized bound is saying, each operation will have some particular cost that we assign it (amortized cost). We are then only required to preserve the sum of these costs. That is,


\sum \mbox{actual cost} \leq \sum \mbox{amortized cost}

If we know that the amortized cost is at most constant, then we know that the actual cost is at most constant. This abstracts away costs of individual operations, only focusing on the overall cost.


Links

See https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-046j-design-and-analysis-of-algorithms-spring-2015/lecture-notes/MIT6_046JS15_lec05.pdf

Flags