Amortization/Accounting Method: Difference between revisions
From charlesreid1
(Created page with "The accounting method is a way of amortizing operations that performs an accounting or balancing method over the time utilized for different operations. The canonical example...") |
No edit summary |
||
| Line 2: | Line 2: | ||
The canonical example is insertions and deletions. When we insert an item into a sorted structure, we pay log(N) cost to insert that item, and therefore pay log(N) cost when we insert it. The accounting method then allows us to account for that cost, adding a "log(N)" coin to our bank account. Then when we remove the item, we have already spent the log(N) cost to insert it, and we can spend that "log(N)" coin to remove the item without an amortized cost. | The canonical example is insertions and deletions. When we insert an item into a sorted structure, we pay log(N) cost to insert that item, and therefore pay log(N) cost when we insert it. The accounting method then allows us to account for that cost, adding a "log(N)" coin to our bank account. Then when we remove the item, we have already spent the log(N) cost to insert it, and we can spend that "log(N)" coin to remove the item without an amortized cost. | ||
{{AlgorithmsFlag}} | |||
[[Category:Amortization]] | |||
Revision as of 07:24, 2 July 2017
The accounting method is a way of amortizing operations that performs an accounting or balancing method over the time utilized for different operations.
The canonical example is insertions and deletions. When we insert an item into a sorted structure, we pay log(N) cost to insert that item, and therefore pay log(N) cost when we insert it. The accounting method then allows us to account for that cost, adding a "log(N)" coin to our bank account. Then when we remove the item, we have already spent the log(N) cost to insert it, and we can spend that "log(N)" coin to remove the item without an amortized cost.
 |
Algorithms Part of Computer Science Notes
Series on Algorithms
Algorithms/Sort · Algorithmic Analysis of Sort Functions · Divide and Conquer · Divide and Conquer/Master Theorem Three solid O(n log n) search algorithms: Merge Sort · Heap Sort · Quick Sort Algorithm Analysis/Merge Sort · Algorithm Analysis/Randomized Quick Sort
Algorithms/Search · Binary Search · Binary Search Modifications
Algorithms/Combinatorics · Algorithms/Combinatorics and Heuristics · Algorithms/Optimization · Divide and Conquer
Algorithms/Strings · Algorithm Analysis/Substring Pattern Matching
Algorithm complexity · Theta vs Big O Amortization · Amortization/Aggregate Method · Amortization/Accounting Method Algorithm Analysis/Matrix Multiplication
Estimation Estimation · Estimation/BitsAndBytes
Algorithm Practice and Writeups Project Euler · Five Letter Words · Letter Coverage
|