Senior LevelData Structures & Algorithms
Explain Amortised Analysis with Aggregate, Accounting, and Potential methods.
ā Interview Prompt: Describe the three methods of amortised analysis ā Aggregate, Accounting (Banker's), and Potential (Physicist's) ā with examples.
Amortised Analysis assigns average performance per operation over a sequence of operations, even if individual operations are expensive.
1. Aggregate Method:
Total cost of $N$ operations / $N$ = amortised cost.
ā¢
Example: Dynamic array push ā $N$ pushes cost $O(N)$ total (occasional $O(N)$ doubling) ā $O(1)$ amortised.
2. Accounting (Banker's) Method:
Assign credits to cheap operations to "bank" for future expensive ones.
ā¢
Dynamic array: charge 3 per push (1 for this push, 2 saved to pay for future copy).
3. Potential Method:
Define a potential function $\Phi$ representing "stored energy".
ā¢
Amortised cost = actual cost + $\Delta\Phi$.
ā¢
$\sum$ amortised cost $\geq$ $\sum$ actual cost (valid analysis).
Code Implementation Example
typescript
// Dynamic Array ā O(1) amortised push (Aggregate method proof)
class DynamicArray<T> {
private data: T[] = new Array(1);
private size = 0;
push(val: T): void {
if (this.size === this.data.length) {
// Double capacity ā O(N) but amortised O(1) since done every N pushes
const newData = new Array(this.data.length * 2);
for (let i = 0; i < this.size; i++) newData[i] = this.data[i];
this.data = newData;
}
this.data[this.size++] = val; // O(1) most of the time
}
}
// Total cost of N pushes: 1+1+2+1+1+1+1+4+... = O(N) ā O(1) amortisedš”Dynamic array doubling strategy ā O(1) amortised push via aggregate analysis.
šÆ Interview Key Takeaway
Amortised O(1) is crucial for understanding dynamic arrays, Union-Find, splay trees, and many advanced data structures used in production systems.
#DSA#Amortised Analysis#Theory#Complexity#Senior
Back to all Data Structures & Algorithms Questionsā