---

📘 Amortized Analysis (Introduction)

Amortized Analysis is a method used to analyze the average performance of each operation in a sequence of operations in the worst case.

👉 It measures the long-term average cost of operations, even if some individual operations are expensive.

Why Not Average-Case?

Average-case analysis requires probability distribution of inputs.
Amortized analysis does not rely on probability.

Instead, it assumes:

• A sequence of operations
• Some operations may be expensive
• Over time, the expensive operations occur rarely
• So, amortized cost becomes small

---

📌 When is Amortized Analysis Used?

Common in data structures where:

• Most operations are cheap
• Few operations are expensive but rare

Examples:

1. Dynamic Array (ArrayList / Vector) resizing
2. Stack operations with multipop
3. Union-Find (Disjoint Set Union) with path compression
4. Splay trees
5. Incrementing a binary counter

---

📘 Why Amortized Analysis is Important?

• More realistic than worst-case
• Avoids needing probability assumptions (unlike probabilistic analysis)
• Shows how some DS achieve “average O(1)” operations
• Important for competitive programming and interviews

---

📘 Three Methods of Amortized Analysis

---

1. Aggregate Method (Simplest)

Calculate the total cost of n operations and divide by n.

Example: Dynamic Array Insertion

When an array is full, it doubles its size.

Some operations:

• Most insertions: O(1)
• Expansion (copying all items): O(n)

If we perform n insertions:

• Total cost = n (regular inserts) + n (for resizing steps)
  = 2n
  Amortized cost = (2n)/n = O(1) per operation

✔ Even though resizing is expensive, it happens rarely
✔ So average over time = constant

---

2. Accounting Method (Banker’s Method)

Assign a charged cost to each operation:

• Some cost used now
• Extra “saved” for future expensive operations

Example: Dynamic Array

Actual costs:

• Normal insert = 1 unit
• Resize insert = n units (copy all elements)

We assign:

• Charge = 3 units for every insert
  • 1 used for actual insert
  • 2 saved in “bank”

These saved units are used to pay the future expensive resize operations.

Result: Amortized = 3 units = O(1)

---

3. Potential Method (Physicist’s Method)

Define a potential function that stores energy (credit) in the data structure.

Amortized cost =
[
\text{Actual cost} + (\text{Potential after} – \text{Potential before})
]

Potential increases during cheap operations and is used up during expensive ones.

Example: Dynamic Array

Define potential Φ = number of unused slots.
When array is full, Φ = 0
Expanding increases Φ to large number.

Using this method, amortized cost again becomes O(1).

---

📘 Classic Examples of Amortized Analysis

---

✔ Example 1: Dynamic Array (Vector) Insertion

• Regular insert → O(1)
• Resize (double array) → O(n)

Amortized time = O(1)

---

✔ Example 2: Stack Multipop Operation

Stack supports:

• push(x): O(1)
• pop(): O(1)
• multipop(k): pop up to k elements

Worst-case multipop = O(n)

But total number of pops ≤ total pushes.

For n operations:
Total cost ≤ O(n)
Amortized = O(1)

---

✔ Example 3: Incrementing a Binary Counter

Binary counter increments like:

0111 + 1 = 1000

Worst-case increment = O(n)
But most increments = O(1)

Total operations for n increments = 2n
Amortized = O(1)

---

✔ Example 4: Union-Find with Path Compression

Union-Find operations:

• find
• union

With path compression + union by rank:

Amortized time = O(α(n))

Where α(n) = Inverse Ackermann function
(which grows extremely slowly, almost constant)

---

📘 Key Differences: Worst Case vs Amortized vs Average Case

Type	Meaning	Depends on Probability?
Worst-case	Maximum time for any input	No
Average-case	Expected time over all inputs	Yes
Amortized	Average time over sequence of operations	No

---

📘 Short Summary (Exam Notes)

• Amortized Analysis → long-term average cost of operations
• Used when occasional expensive operations occur
• Methods:
  ✔ Aggregate
  ✔ Accounting
  ✔ Potential
• Applications:
  ✔ Dynamic array resizing
  ✔ Stack multipop
  ✔ Binary counter increment
  ✔ Union-Find
• Amortized time often O(1) for many operations
• Does NOT use probability → not same as average-case

---