Amortized Analysis
Nishant Mehta
219
Lecture 18
s
Amortized Analysis
Amortized analysis is a way of doing worst-case analysis by bounding the average cost to perform each operation (averaged over the sequence of operations)
Motivation: Some operations might be very expensive, but they happen infrequently, so on average each operation might have low cost
Amortized Analysis is not related to Average-Case Analysis; amortized analysis doesn’t use probability or expected value
The peril of per-operation worst-case analysis Example: Stack S
OCI ) 0111
Suppose that in addition to having the usual PUSH and POP operation, we also have an operation KPOP
KPOP(S, k): Pop top k elements on stack (or all elements if less than k elements are on stack)
01kt
Worst-case cost of sequence of n PUSH, POP, and KPOP
Worst-case cost of KPOP operation?
operations?
Oink
)
Aggregate analysis
Aggregate analysis bounds worst-case runtime in aggregate (over whole sequence of operations), rather than giving worst-case bounds for each operation separately (without consideration of previous operations)
Example: Stack with KPOP
• •
•
Cost of each KPOP is simply the number of actual pops that happen within it
Total number of pops is at most total number of pushes (at most n)
So, any sequence of n pushes, pops, and KPOPs takes at most O(n) time
Aggregate analysis
Aggregate analysis bounds worst-case runtime in aggregate (over whole sequence of operations), rather than giving worst-case bounds for each operation separately (without consideration of previous operations)
Example: Stack with KPOP
• •
•
Cost of each KPOP is simply the number of actual pops that happen within it
Total number of pops is at most total number of pushes (at most n)
So, any sequence of n pushes, pops, and KPOPs takes at most O(n) time
Accounting method
In the accounting method, for each operation we charge an amortized cost
•
For the ith operation:
ci is actual cost ˆci is amortized cost
we charge the actualcost Ci Interpretation of ˆci > ci ? plus credit (Ei – ci)
Goal: select amortized costs such that we have:
The amortized cost of an operation can be greater than (or less than!!) the actual cost
Actual cost
Xn Xn Upper bound on runtime! ci ˆci
i=1 i=1
Accounting Method – Stack with KPOP example
ith operation
if ith operation if ith op.
=L
( Pdt
if
i s PUSH
:
E,
the
is
Pop : §.
(already paid fr by some Push! [Ci- I)
is Krol :
di
– –
fan
pops
are
already paidfor)
§, I.
some actual costs Ci though I i small
large ,
=
O
”
e E?– an
1 for actual cost g. =/ and prepay l b/c eventually
element might be popped)
pushed
Even
all dmoritired costs ^ are
a re
Incrementing binary counter example
k-bit counter with INCREMENT
INCREMENT:
i =0
while i < k and A[i] == 1
decimal 00000000 :0
00000001 00000010 00000011 00000100 4 00000101 g- 00000110 , 00000111 7-
K
--
8
A[7] A[6] A[5] A[4] A[3] A[2] A[1] A[0]
A[i] = 0
i = i +1 if i < k
A[i] = 1
analysis "
naive case operation
is
Ock)
0 0(0 0 1 0 0 0
→ o O O O O O 00 → nk)- worst- case ofn increments
worst - when
increment
A- llllllll
3
Worst-case cost of n INCREMENT operations?
i cost e
Aggregate analysis: A- lo l A- Cll
A fin
: I
changes changes
changes
n times 12 times
7, time '
total
Ii
=
2n
en
!II. on
Incrementing binary counter example
k-bit counter with INCREMENT
INCREMENT:
i =0
while i < k and A[i] == 1
A[i] = 0
i = i +1 if i < k
A[i] = 1
ci -00000000
100000001 200000010 100000011 300000100 100000101 200000110 100000111 400001000
A[7] A[6] A[5] A[4] A[3] A[2] A[1] A[0]
Worst-case cost of n INCREMENT operations? Accounting method:
Incrementing binary counter example
k-bit counter with INCREMENT INCREMENT:
i =0
while i < k and A[i] == 1
A[i] = 0
i = i +1 if i < k
A[i] = 1
ci -00000000
100000001 200000010 100000011 300000100 100000101 200000110 100000111 400001000
A[7] A[6] A[5] A[4] A[3] A[2] A[1] A[0]
-$1 -$1
-$1 -$1
Worst-case cost of n INCREMENT operations? Accounting method: 0 will be set to l .
In one operation at most a single
k$1 for actual o → I ,
)
di E ' = 2n
when a when
, charge $2 O is set to l i
$1 to prep¥ay
for I→ O
? Ci e en,
I
is set to 0 , charge $0
.
total cost
,
Incrementing binarfy counter example
cumulation t
- -
I 2
3 4 46
7- 8 8 10
10 12 11 14
1516
k-bit counter with INCREMENT INCREMENT:
ˆci ci --00000000 2100000001 2200000010 2100000011 2300000100 2100000101 2200000110 2100000111 2400001000
cumulative
A[7] A[6] A[5] A[4] A[3] A[2] A[1] A[0]
i =0
while i < k and A[i] == 1
A[i] = 0
i = i +1 if i < k
A[i] = 1
-$1 -$1
-$1 -$1
Worst-case cost of n INCREMENT operations? Accounting method: 0 will be set to l .
In one operation at most a single
k$1 for actual o → I ,
)
di E ' = 2n
when a when
, charge $2 O is set to l i
$1 to prep¥ay
for I→ O
? Ci e en,
l
is set to 0 , charge $0
.
total cost
,
Dynamic tables
We want a table which can support a stream of INSERT and DELETE operations
Like with hash tables, we define the load factor of table T
to be:
↵(T) =
When the load factor is 1 and a new INSERT operation arrives,
we need to increase the size of the table.
We also want the load factor to be lower bounded by a positive constant (let’s use 1/2) to ensure that we are using at least a constant fraction of the allocated space.
[# of elements stored in T] [size of T]
Dynamic tables
T.
How can we insert an element x when the load factor is 1 (so the table T is full)? We need to resize the table. For simplicity let’s suppose the table is of size at least 1.
INSERT(T, x ):
if T.n == T.size
slots n
-
*
of
n
=
stored
T
# of
elements in table
Allocate new table Tnew of size 2 · T.size gotra: Insert all items in T into Tnew
in
T = Tnew Insert x into T
T.n = T.n + 1
Dynamic Tables - Accounting Method
credit - prepaying
Each insertion - charge $3, broken down as:
•
$1 for the insertion itself (this is the actual cost)
•
$1 credit for moving this item
$2 credit for use upon resize operation:
•
•
$1 credit for moving an item that has already been moved (such an item has no credit anymore as it used up its credit when it was moved the first time)
- $4
DAios
Insertion
redistributed wealth y,
each has
insertion amortized cost
A §.
=3
Koki i:$ iI# I$
D itto T#$ol$ol$ol$4XTHX
Dynamic Tables - Accounting Method
What about shrinking the table once the table is too empty?
By symmetry, you might think “let’s halve the table when it’s less than half empty,” but this is problematic. Two ways to see why:
(1) Consider what happens when the load factor is right around 1/2. A deletion triggers a halving, at which point the table is now nearly full. Two insertions trigger a doubling, and the table is right around 1/2 again. Two deletions trigger a halving, etc. This is too expensive!
Dynamic Tables - Accounting Method
What about shrinking the table once the table is too empty?
By symmetry, you might think “let’s halve the table when it’s less than half empty,” but this is problematic. Two ways to see why:
(1) Consider what happens when the load factor is right around 1/2. A deletion triggers a halving, at which point the table is now nearly full. Two insertions trigger a doubling, and the table is right around 1/2 again. Two deletions trigger a halving, etc. This is too expensive!
(2) A halving can happen soon after a doubling (since a doubling brings the load factor close to 1/2). But, after a doubling, nearly all elements have no credit on them. So, we don’t have enough to pay for a halving.
Dynamic Tables - Accounting Method
(2) A halving can happen soon after a doubling (since a doubling brings the load factor close to 1/2). But, after a doubling, nearly all elements have no credit on them. So, we don’t have enough to pay for a halving.
Ah, why don’t we postpone halving until after we have built up enough credit. Let’s charge $2 for each deletion:
• $1 for the actual deletion itself (this is the actual cost)
• $1 credit to pay for moving an item upon a halving operation
When have we earned enough credit to do a halving? When the table has load ≤ 1/4. Why? Since the most recent doubling
operation, we have deleted at least a quarter of the table. Thus, we have enough credit to move a quarter of the table upon deletion.
Deletion#
generates
1
Ftl F -delete
in
' q
delete
-
--
di ,Tignoring# delete
T$ol$ol$ol$HXfXlX
T§$ll$o/XlxlxlxIX TH$oIX1X
extra $ 2
--2 .
a
=
( Delete n
%,, I3 =it
:
For runtime
sequence
di s
of any
Insert
operations
§ max -13,27
=
,
CiEIi . =3n
Dynamic Tables - Accounting Method
(2) A halving can happen soon after a doubling (since a doubling brings the load factor close to 1/2). But, after a doubling, nearly all elements have no credit on them. So, we don’t have enough to pay for a halving.
Ah, why don’t we postpone halving until after we have built up enough credit. Let’s charge $2 for each deletion:
• $1 for the actual deletion itself (this is the actual cost)
• $1 credit to pay for moving an item upon a halving operation
When have we earned enough credit to do a halving? When the table has load ≤ 1/4. Why? Since the most recent doubling
operation, we have deleted at least a quarter of the table. Thus, we have enough credit to move a quarter of the table upon deletion.