Encyclopedia > Amortized time

  Article Content

Amortized analysis

Redirected from Amortized time

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:

  1. Aggregate analysis[?] - determines upper bound T(n) on total cost of sequence of n operations, then calculates average cost to be T(n)/n
  2. Accounting method[?] - determines the individual cost of each operation.
  3. Potential method[?] - like Accounting method, but the method overcharges operations early to compensate for undercharges later.



All Wikipedia text is available under the terms of the GNU Free Documentation License

 
  Search Encyclopedia

Search over one million articles, find something about almost anything!
 
 
  
  Featured Article
Canadian Charter of Rights and Freedoms

... by the Universal Declaration of Human Rights. A key drafter of both the Universal Declaration and the Canadian Charter was Professor John Peters Humphrey, the Canadian ...

 
 
 
This page was created in 37.5 ms