Amortized Analysis

Question 1

What is amortized analysis?

Answer 1

A technique for analyzing the average cost per operation over a sequence of operations, ensuring worst-case performance bounds without using probability.

Question 2

How is amortized analysis different from average-case analysis?

Answer 2

Amortized analysis provides worst-case guarantees over sequences, while average-case uses probabilities and expectations.

Question 3

When is amortized analysis useful?

Answer 3

When a few operations are expensive but are ‘paid for’ by many cheap operations.

Question 4

What are the three main methods of amortized analysis?

Answer 4

1. Aggregate
2. Accounting
3. Potential methods.

Question 5

What is the Aggregate Method?

Answer 5

Calculate total cost T(n) of n operations, then amortized cost = T(n)/n.

Question 6

What is the Accounting Method?

Answer 6

Overcharge some operations, store the surplus as ‘credit,’ and use it to pay for more expensive future operations.

Question 7

What must the credit total always be in the accounting method?

Answer 7

Non-negative — credit can’t go below zero.

Question 8

What is the Potential Method?

Answer 8

Uses a potential function Φ to represent stored work (like energy) in the whole data structure.

Question 9

Formula for amortized cost in the Potential Method?

Answer 9

ĉᵢ = cᵢ + Φ(Dᵢ) - Φ(Dᵢ₋₁)

Question 10

What’s the worst-case time for MULTIPOP?

Answer 10

O(n), if the stack has n items.

Question 11

Aggregate cost of n stack operations (including MULTIPOP)?

Answer 11

O(n), since each item can only be popped once.

Question 12

Amortized cost of stack operations using accounting?

Answer 12

PUSH = 2 units, POP/MULTIPOP = 0 units.

Question 13

Potential function for stack (Potential Method)?

Answer 13

Φ = number of items in the stack

Question 14

What causes cost in INCREMENT operation?

Answer 14

Flipping bits from 1 to 0 and a 0 to 1.

Question 15

Worst-case time for a single increment?

Answer 15

O(k), where k is the number of bits.

Question 16

Aggregate total cost of n increments?

Answer 16

Question 17

Amortized cost per increment (any method)?

Answer 17

O(1), often exactly 2.

Question 18

How does the accounting method pay for bit flips?

Answer 18

Pay 2 when setting a bit to 1 (1 now, 1 saved for reset).

Question 19

Potential function for counter?

Answer 19

Φ = number of 1s in the counter

Question 20

What happens when a dynamic array is full during insertion?

Answer 20

Allocate a new array (usually double the size), copy all items, then insert the new one.

Question 21

Worst-case insert time for dynamic array resizing?

Answer 21

O(n) when resize occurs.

Question 22

Total cost of n inserts with resizing?

Answer 22

O(n)

Question 23

Amortized cost per insert for dynamic arrays?

Answer 23

O(1), often shown as 3 using accounting.

Question 24

Accounting method cost breakdown for insert into dynamic arrays?

Answer 24

1 for insert, 1 for future move, 1 for helping move others = 3 units.

Question 25

Why doesn't resizing make total cost quadratic?

Answer 25

Because resizes happen infrequently at 1, 2, 4, 8... forming a geometric series.

Question 26

Front

Answer 26

Back

Question 27

What is a stack?

Answer 27

A linear data structure that follows the Last In, First Out (LIFO) principle.

Question 28

What are the two primary operations of a stack?

Answer 28

`push` (adds an element) and `pop` (removes the top element).

Question 29

What does the `push` operation do?

Answer 29

Adds an element to the top of the stack.

Question 30

What does the `pop` operation do?

Answer 30

Removes and returns the top element of the stack.

Question 31

What is the time complexity of `push` in a standard stack?

Answer 31

O(1) – constant time.

Question 32

What is the time complexity of `pop` in a standard stack?

Answer 32

O(1) – constant time.

Question 33

What is `MULTIPOP(S, k)`?

Answer 33

A special operation that pops up to `k` elements from the stack `S`.

Question 34

What is the worst-case time complexity of `MULTIPOP(S, k)`?

Answer 34

O(k) – up to `k` elements could be removed.

Question 35

What is the aggregate cost of `n` `PUSH`, `POP`, and `MULTIPOP` operations?

Answer 35

O(n) total – each element is pushed and popped at most once.

Question 36

What is the amortized cost of a stack operation (push/pop/multipop)?

Answer 36

O(1) – using aggregate or accounting method.

Question 37

Why is the amortized cost of `MULTIPOP` still O(1)?

Answer 37

Because each element is popped at most once over all operations.

Question 38

What is the LIFO principle?

Answer 38

Last-In, First-Out – the last element added is the first to be removed.

Question 39

What happens if you call `pop` on an empty stack?

Answer 39

It causes an underflow error.

Question 40

What happens if you call `push` on a full stack (in a fixed-size array)?

Answer 40

It causes an overflow error.

Question 41

What data structure is typically used to implement a stack?

Answer 41

Array or singly linked list.

Question 42

What is the potential function used in amortized analysis for stacks?

Answer 42

Typically: Φ(S) = number of elements in the stack.

Question 43

In potential method, what is the amortized cost of a `push`?

Answer 43

ĉ_push = 1 + (Φ_new - Φ_old) = 2

Question 44

In potential method, what is the amortized cost of a `pop`?

Answer 44

ĉ_pop = 1 + (Φ_new - Φ_old) = 0