Amortized analysis

In computer science, amortized analysis is a method for analyzing a given algorithm's complexity, or how much of a resource, especially time or memory, it takes to execute. The motivation for amortized analysis is that looking at the worst-case run time can be too pessimistic. Instead, amortized analysis averages the running times of operations in a sequence over that sequence.^[1]^: 306 As a conclusion: "Amortized analysis is a useful tool that complements other techniques such as worst-case and average-case analysis."^[2]^: 14^[3]

For a given operation of an algorithm, certain situations (e.g., input parametrizations or data structure contents) may imply a significant cost in resources, whereas other situations may not be as costly. The amortized analysis considers both the costly and less costly operations together over the whole sequence of operations. This may include accounting for different types of input, length of the input, and other factors that affect its performance.^[2]

^ Cite error: The named reference tarjan was invoked but never defined (see the help page).
^ ^a ^b Rebecca Fiebrink (2007), Amortized Analysis Explained (PDF), archived from the original (PDF) on 20 October 2013, retrieved 3 May 2011
^ "Lecture 18: Amortized Algorithms". CS312 -Data Structures and Functional Programming. Cornell University. 2006. [Amortized analysis] is different from what is commonly referred to as average case analysis, because amortized analysis does not make any assumption about the distribution of the data values, whereas average case analysis assumes the data are not "bad" (e.g., some sorting algorithms do well on "average" over all input orderings but very badly on certain input orderings). That is, amortized analysis is a worst case analysis, but for a sequence of operations, rather than for individual operations.

[tarjan-1] Cite error: The named reference tarjan was invoked but never defined (see the help page).

[fiebrink-2] Rebecca Fiebrink (2007), Amortized Analysis Explained (PDF), archived from the original (PDF) on 20 October 2013, retrieved 3 May 2011

[3] "Lecture 18: Amortized Algorithms". CS312 -Data Structures and Functional Programming. Cornell University. 2006. [Amortized analysis] is different from what is commonly referred to as average case analysis, because amortized analysis does not make any assumption about the distribution of the data values, whereas average case analysis assumes the data are not "bad" (e.g., some sorting algorithms do well on "average" over all input orderings but very badly on certain input orderings). That is, amortized analysis is a worst case analysis, but for a sequence of operations, rather than for individual operations.

[1]

[2]

[3]