World Library  
Flag as Inappropriate
Email this Article

Amortized analysis

Article Id: WHEBN0000236683
Reproduction Date:

Title: Amortized analysis  
Author: World Heritage Encyclopedia
Language: English
Subject: Linked list, Analysis of algorithms, Fibonacci heap, Splay tree, Hash table
Collection: Analysis of Algorithms
Publisher: World Heritage Encyclopedia

Amortized analysis

In computer science, amortized analysis is a method for analyzing a given algorithm's time complexity, or how much of a resource, especially time or memory in the context of computer programs, it takes to execute. The motivation for amortized analysis is that looking at the worst-case run time per operation can be too pessimistic.[1]

While certain operations for a given algorithm may have a significant cost in resources, other operations may not be as costly. Amortized analysis considers both the costly and less costly operations together over the whole series of operations of the algorithm. This may include accounting for different types of input, length of the input, and other factors that affect its performance.[2]


  • History 1
  • Method 2
  • Examples 3
    • Dynamic Array 3.1
    • Queue 3.2
  • Common use 4
  • References 5


Amortized analysis initially emerged from a method called aggregate analysis, which is now subsumed by amortized analysis. However, the technique was first formally introduced by Robert Tarjan in his 1985 paper Amortized Computational Complexity, which addressed the need for more useful form of analysis than the common probabilistic methods used. Amortization was initially used for very specific types of algorithms, particularly those involving binary trees and union operations. However, it is now ubiquitous and comes into play when analyzing many other algorithms as well.[2]


The method requires knowledge of which series of operations are possible. This is most commonly the case with data structures, which have state that persists between operations. The basic idea is that a worst case operation can alter the state in such a way that the worst case cannot occur again for a long time, thus "amortizing" its cost.

There are generally three methods for performing amortized analysis: the aggregate method, the accounting method, and the potential method. All of these give the same answers, and their usage difference is primarily circumstantial and due to individual preference.[3]

  • Aggregate analysis determines the upper bound T(n) on the total cost of a sequence of n operations, then calculates the amortized cost to be T(n) / n.[3]
  • The accounting method determines the individual cost of each operation, combining its immediate execution time and its influence on the running time of future operations. Usually, many short-running operations accumulate a "debt" of unfavorable state in small increments, while rare long-running operations decrease it drastically.[3]
  • The potential method is like the accounting method, but overcharges operations early to compensate for undercharges later.[3]


Dynamic Array

Amortized Analysis of the Push operation for a Dynamic Array

Consider a dynamic array that grows in size as more elements are added to it such as an ArrayList in Java. If we started out with a dynamic array of size 4, it would take constant time to push four elements onto it. Yet pushing a fifth element onto that array would take longer as the array would have to create a new array of double the current size (8), copy the old elements onto the new array, and then add the new element. The next three push operations would similarly take constant time, and then the subsequent addition would require another slow doubling of the array size.

In general if we consider an arbitrary number of pushes n to an array of size n, we notice that push operations take constant time except for the last one which takes O(n) time to perform the size doubling operation. Since there were n operations total we can take the average of this and find that for pushing elements onto the dynamic array takes :O(\tfrac{n}{n}) = O(1), constant time.[3]


Let's look at a Ruby implementation of a Queue, a FIFO data structure:

class Queue
  def initialize
    @input = []
    @output = []

  def enqueue(element)
    @input << element

  def dequeue
    if @output.empty?
      while @input.any?
        @output << @input.pop


The enqueue operation just pushes an element onto the input array; this operation does not depend on the lengths of either input or output and therefore runs in constant time.

However the dequeue operation is more complicated. If the output array already has some elements in it, then dequeue runs in constant time; otherwise, dequeue takes O(n) time to add all the elements onto the output array from the input array, where n is the current length of the input array. After copying n elements from input, we can perform n dequeue operations, each taking constant time, before the output array is empty again. Thus, we can perform a sequence of n dequeue operations in only O(n) time, which implies that the amortized time of each dequeue operation is O(1).[4]

Alternatively, we can charge the cost of copying any item from the input array to the output array to the earlier enqueue operation for that item. This charging scheme doubles the amortized time for enqueue, but reduces the amortized time for dequeue to O(1).

Common use

  • In common usage, an "amortized algorithm" is one that an amortized analysis has shown to perform well.
  • Online algorithms commonly use amortized analysis.


  1. ^ "Lecture 7: Amortized Analysis" (PDF). Retrieved 14 March 2015. 
  2. ^ a b Rebecca Fiebrink (2007), Amortized Analysis Explained (PDF), retrieved 2011-05-03 
  3. ^ a b c d e "Lecture 20: Amortized Analysis". Cornell University. Retrieved 14 March 2015. 
  4. ^ Grossman, Dan. "CSE332: Data Abstractions" (PDF). Retrieved 14 March 2015. 
This article was sourced from Creative Commons Attribution-ShareAlike License; additional terms may apply. World Heritage Encyclopedia content is assembled from numerous content providers, Open Access Publishing, and in compliance with The Fair Access to Science and Technology Research Act (FASTR), Wikimedia Foundation, Inc., Public Library of Science, The Encyclopedia of Life, Open Book Publishers (OBP), PubMed, U.S. National Library of Medicine, National Center for Biotechnology Information, U.S. National Library of Medicine, National Institutes of Health (NIH), U.S. Department of Health & Human Services, and, which sources content from all federal, state, local, tribal, and territorial government publication portals (.gov, .mil, .edu). Funding for and content contributors is made possible from the U.S. Congress, E-Government Act of 2002.
Crowd sourced content that is contributed to World Heritage Encyclopedia is peer reviewed and edited by our editorial staff to ensure quality scholarly research articles.
By using this site, you agree to the Terms of Use and Privacy Policy. World Heritage Encyclopedia™ is a registered trademark of the World Public Library Association, a non-profit organization.

Copyright © World Library Foundation. All rights reserved. eBooks from Project Gutenberg are sponsored by the World Library Foundation,
a 501c(4) Member's Support Non-Profit Organization, and is NOT affiliated with any governmental agency or department.