Amortized O(1) operations — Hinglish notes

3.3.7 · Coding › Hashing

KIYA hai amortization?

Teen standard methods:

Aggregate method — total cost / n.
Accounting method — har saste op ko thoda extra charge karo ("credit") taaki future ke expensive ops pre-pay ho sakein.
Potential method — ek potential function $Φ$ define karo jo "bacha hua" kaam store kare.

KYUN ek hash table / dynamic array ko yeh chahiye?

KAISE: doubling cost ko scratch se derive karna

Maan lo hum empty se shuru karte hain aur $n$ items push karte hain. Jab bhi array full ho, hum capacity double karte hain. Capacities jo milti hain: $1, 2, 4, 8, \dots$

Step 1 — saste inserts. $n$ mein se har ek push element likhne ke liye $1$ cost karta hai. $cheap cost = n$ Yeh step kyun? Har element exactly ek baar apni slot mein likha jaata hai.

Step 2 — resizes par copy costs. Capacity $2^{k}$ par resize $2^{k}$ purane elements copy karta hai. Resizes sizes $1, 2, 4, \dots, 2^{m}$ par hote hain jahan $2^{m} \leq n$ . $copy cost = 1 + 2 + 4 + \dots + 2^{m} = \sum_{i = 0}^{m} 2^{i} = 2^{m + 1} - 1$ Yeh step kyun? Geometric series — har doubling current poore array ko ek baar copy karta hai.

Step 3 — sum ko bound karo. Kyunki $2^{m} \leq n$ hai, hame $2^{m + 1} - 1 < 2 n$ milta hai. $copy cost < 2 n$

Step 4 — total aur divide. $Total = n + 2 n = 3 n = O (n)$ $Amortized cost per push = \frac{3 n}{n} = 3 = O (1)$

Yeh kyun kaam karta hai: copies ek geometric series banate hain jo $n$ ke constant multiple mein sum hoti hai, $n^{2}$ mein nahi. Rare doublings "pay" hoti hain unse pehle ke kaafi saare saste inserts se.

Accounting Method ("3" ke liye intuition)

Potential Method (formal)

Worked Examples

Common Mistakes

Flashcards

"Amortized O(1)" ka precise matlab kya hai?

n operations ki total cost O(n) hai, toh sequence mein average cost per operation O(1) hai — yeh sequence par worst-case guarantee hai, single op per nahi.

Array capacity doubling amortized O(1) per insert kyun hai?

Copy costs geometric series 1+2+4+…+2^m < 2n banate hain, plus n writes → total 3n = O(n), toh 3 per op.

Har baar +1 se grow karne par total copy cost aur amortized cost kya hai?

Copy cost = n(n-1)/2 = O(n²); amortized = O(n), constant nahi.

Amortized aur average-case complexity mein kya fark hai?

Amortized = sequence par deterministic worst-case; average-case = inputs ki probability distribution par expectation.

Dynamic array doubling ke liye use ki gayi potential function batao.

Φ = 2·size − capacity (≥0 jab ≥ aadha bhar ho).

Accounting method mein har push ko kitna charge hota hai aur kyun?

3 units: 1 write ke liye, 2 credit ke roop mein save hote hain future mein apni aur ek neighbour ki copies pay karne ke liye.

Real-time systems mein amortized O(1) acceptable kyun nahi ho sakta?

Ek single resize O(n) hai — ek latency spike — chahe average constant ho.

Amortized O(1) inserts guarantee karne ke liye growth factor ki kya requirement hai?

Multiplicative (geometric) growth kisi bhi factor > 1 se; additive growth fail ho jaati hai.

Recall Feynman: ek 12-saal ke bacche ko samjhao

Socho tum ek chote se box mein khilone bhar rahe ho. Jab woh bhar jaata hai, tum ek box do guna bada khareed te ho aur saare khilone us mein move karte ho — yeh move slow hota hai. Lekin kyunki har naya box pichle se double hota hai, saikdon khilone ke baad bhi tum khilone sirf kuch hi baar move karte ho. Toh zyaadatar time khilona add karna bahut fast hai, aur rare slow moves spread out karne par chhoti lagte hain. Average mein, ek khilona add karna fast hai — yahi "amortized O(1)" hai.

Connections

Dynamic Arrays — geometric resizing ka primary use case.
Hash Tables — load-factor threshold par rehashing yahi argument use karta hai.
Load Factor — open addressing mein resize trigger karta hai.
Geometric Series — yeh math hai jo doubling ko linear rakhti hai.
Big-O Notation — amortized asymptotic analysis ka ek flavor hai.
Potential Method — yahan use ki gayi formal accounting technique.
Stack with Multipop — amortized analysis ka ek aur classic example.