Science Fair Project Encyclopedia In computational complexity
theory, amortized analysis is the time per operation averaged
over a worst-case sequence of operations. Amortized analysis
differs from average-case performance in that probability is not
involved; amortized analysis guarantees the time per operation
over worst-case performance. There are several techniques used
in amortized analysis: - Aggregate analysis determines the upper
bound T(n) on the total cost of a sequence of n operations, then
calculates the average cost to be T(n)/n. - Accounting method
determines the individual cost of each operation. - Potential
method is like the accounting method, but overcharges operations
early to compensate for undercharges later. The contents of this
article is licensed from www.wikipedia.org under the GNU Free
Documentation License. Click here to see the transparent copy
and copyright details