Amortized Analysis
Operations don’t stand alone!
Often, we perform _________ of operations on data structures
and we are interested in the time complexity of the
__________________
Definition: worst-case sequence complexity (WCSC)
WCSC m * worst-case time complexity of any one operation
in a sequence of m operations
Amortized Sequence Complexity
Definition: amortized sequence complexity
• Represents the “average” worst-case complexity of each
operation
• Different than average-case time (no probability!)
• Often makes more sense in real situation
Approaches to Calculating Amortized Complexity
• Aggregate
• Accounting
• Potential
Binary Counters (from CS Unplugged)
CS Unplugged video
Fun Video
Binary Counters
Suppose we are counting up with a binary counter:
when does the 1’s digit get flipped?
when does the 2’s digit get flipped?
what about the 4’s digit?
Zoom Chat
Binary Counter: Aggregate Approach
Initial counter 00000 Value = 0
After INCREMENT 00001 Value = 1 Cost = 1
After INCREMENT 00010 Value = 2 Cost =
After INCREMENT Value = 3 Cost =
After INCREMENT Value = 4 Cost =
After INCREMENT Value = 5 Cost =
After INCREMENT Cost =
…
After INCREMENT Cost =
After INCREMENT Cost =
After INCREMENT Cost =
After INCREMENT Cost =
Chalk Talk
Binary Counter = sequence of k
bits (k fixed) with single
operation: INCREMENT
Chalk Talk
Chalk Talk
Multipop Stack
• A stack with the regular PUSH and POP operations
• Each take O(1) time
•
Worksheet Multipop Stack: Aggregate Approach
Accounting Approach
Charge each operation an amortized cost
•
•
When amortized cost > actual cost
•
When amortized cost < actual cost
•
Can NEVER be in debt
Chalk Talk Accounting Approach: Multipop Stack
Binary Counter: Aggregate Approach
Initial counter 00000 Value = 0
After INCREMENT 00001 Value = 1 Cost = 1
After INCREMENT 00010 Value = 2 Cost =
After INCREMENT Value = 3 Cost =
After INCREMENT Value = 4 Cost =
After INCREMENT Value = 5 Cost =
After INCREMENT Cost =
…
After INCREMENT Cost =
After INCREMENT Cost =
After INCREMENT Cost =
After INCREMENT Cost =
Worksheet
Binary Counter = sequence of k
bits (k fixed) with single
operation: INCREMENT
Worksheet Accounting Approach: Binary Counter
Dynamic Arrays: Reminder
Dynamic Arrays: Copying ElementsChalk Talk
Worksheet Dynamic Arrays: Accounting method
Worksheet Dynamic Arrays: Aggregate method
Worksheet Dynamic Arrays: Aggregate method