COMP251: Amortized Analysis
Jérôme Waldispühl School of Computer Science
McGill University
Based on (Cormen et al., 2009)
Overview
• Analyze a sequence of operations on a data structure.
• We will talk about average cost in the worst case (i.e. not averaging over a distribution of inputs. No probability!)
• Goal: Show that although some individual operations may be expensive, on average the cost per operation is small.
• 3 methods:
1. aggregate analysis
2. accounting method
3. potential method (See textbook for more details)
Aggregate analysis
Stack operations
• PUSH(S, x): O(1) each ⇒ O(n) for any sequence of n operations.
• POP(S): O(1) each ⇒ O(n) for any sequence of n operations. • MULTIPOP(S,k):
while S≠Ø and k>0 do POP(S)
k⟵k−1
Running time of MULTIPOP?
Running time of multiple operations
Running time of MULTIPOP:
• Let each PUSH/POP cost 1.
• # of iterations of while loop is min(s, k), where s = # of objects on
stack. Therefore, total cost = min(s, k).
Sequence of n PUSH, POP, MULTIPOP operations:
• Worst-case cost of MULTIPOP is O(n).
• Have n operations.
• Therefore, worst-case cost of sequence is O(n2).
But:
• Each object can be popped only once per time that it is pushed.
• Have ≤ n PUSHes ⇒ ≤ n POPs, including those in MULTIPOP.
• Therefore, total cost = O(n).
• Average over the n operations ⇒ O(1) per operation on average.
Binary counter
• k-bit binary counter A[0 . . k − 1] of bits, where A[0] is the
least significant bit and A[k − 1] is the most significant bit.
• Counts upward from 0. k−1
• To increment, add 1 (mod 2k ): Increment(A,k):
i←0
while i
Table expansion
Consider only insertion.
• When the table becomes full, double its size and reinsert all existing items.
• Guarantees that α ≥ 1⁄2.
• Each time we insert an item into the table, it is an elementary insertion.
TABLE-INSERT(T,x) if size[T ]=0
then allocate table[T] with 1 slot size[T]←1
if num[T]=size[T] then
allocate new-table with 2 · size[T] slots insert all items in table[T] into new-table free table[T]
table[T]←new-table
size[T]←2·size[T]
insert x into table[T]
num[T]←num[T] + 1 (Initially, num[T]=size[T]= 0)
Aggregate analysis
• Cost of 1 per elementary insertion.
• Count only elementary insertions (other costs = constant). ci = actual cost of ith operation
• If not full, ci =1.
• If full, have i−1 items in the table at the start of the ith operation.
Have to copy all i − 1 existing items, then insert ith item ⇒ ci = i. Naïve: n operations ⇒ ci = O(n) ⇒ O(n2) time for n operations
”
ci=$#i ifi−1ispowerof2
$% 1 Otherwise n “#logn$%
2″#logn$%+1 −1
2−1