3.1.5
Intuition Badi picture (WHY yeh exist karta hai)Kuch operations kabhi kabhi expensive hote hain par zyaadatar cheap . Agar tum unhe unke worst single case se bound karo, toh tum sach se zyada bol rahe ho. Example: ek dynamic array ka push O ( 1 ) O ( n ) poore operations ke sequence par, ek operation ki average cost kya hai — guaranteed, probabilistic nahi?
Key word: guaranteed . Amortized = randomness nahi hai. Hum promise karte hain ki koi bhi m m ⋅ ( amortized cost )
Definition Amortized costMaano m total actual cost T ( m ) amortized cost per operation koi bhi value c ^ ∑ i = 1 m c ^ i ≥ ∑ i = 1 m c i (actual cost) c ^ = m 1 ∑ c ^ i honest hai kyunki left side real total work ko upper-bound karti hai.
c ^ teen methods hain. Sab same total bound dete hain; farq sirf accounting ke tarike mein hai.
Total cost T ( m ) m = T ( m ) / m same amortized cost milti hai. Sochne mein sabse simple, jab operations alag hon toh weak.
Worked example Dynamic array (table doubling),m KAISE: Capacity 1 se start karo. Jab full ho jaye, double allocate karo aur copy karo.
Sasta part: har push 1 element likhta hai ⇒ m
Expensive part (copies): hum tab copy karte hain jab size 1 , 2 , 4 , 8 , … 1 + 2 + 4 + ⋯ + 2 k 2 k ≤ m
Yeh step kyon? Copy sizes ek geometric series banate hain. Crucial fact yeh hai:
1 + 2 + 4 + ⋯ + 2 k = 2 k + 1 − 1 < 2 m . Total: T ( m ) ≤ m + 2 m = 3 m Amortized: c ^ = T ( m ) / m ≤ 3 === O ( 1 ) ==
Common mistake Steel-man: "doublingn O ( n ) Yeh sahi kyon lagta hai: woh single expensive push sach mein n Fix: woh O ( n ) har n hota hai. Expensive events rare aur geometrically spaced hain, isliye copies total mein < 2 m m ⋅ n
Har operation ko ek amortized cost c ^ zyada ho sakti hai. Surplus ko data-structure elements par credit ke roop mein store karo. Baad mein, expensive operations user ko charge karne ki jagah stored credit kharcha karte hain. Rule jo ise valid banata hai:
total credit = ∑ ( c ^ i − c i ) ≥ 0 hamesha. ∑ c ^ ≥ ∑ c
Worked example Dynamic array, accounting styleKAISE: c ^ = 3 1
$1 spend karo nayi element place karne ke liye.
$1 nayi element par store karo (baad mein khud ko move karne ke liye pay karne ke liye).
$1 ek purani element par store karo jiske paas abhi credit nahi hai.
Yeh step kyon? Jab array n 2 n n n prepaid hai — credit kabhi negative nahi jata.
Amortized: c ^ = 3 = O ( 1 )
Worked example Binary counter increment (k-bit)increment ki cost = bits flip hue ki sankhya.
Accounting: har increment par $2 charge karo. Ek bit 0 → 1 1 → 0 apne stored $1 se pay karo.
Valid kyon: har 1 === O ( 1 ) == k
Intuition KYA (sabse powerful, sabse reusable)Ek potential function Φ ( D ) D plus potential mein change hai:
c ^ i = c i + Φ ( D i ) − Φ ( D i − 1 ) YEH KAISE KAAM KARTA HAI (telescoping derive karo):
∑ i = 1 m c ^ i = ∑ i = 1 m c i + ( Φ ( D m ) − Φ ( D 0 ) ) . Φ ( D m ) ≥ Φ ( D 0 ) Φ ≥ 0 Φ ( D 0 ) = 0 ∑ c ^ i ≥ ∑ c i .
Worked example Dynamic array potential ke zariye —Φ n s Φ Choose Φ = 2 n − s n ≥ s /2 ≥ 0 n ≥ s /2 ⇒ 2 n ≥ s
Non-resizing push (n → n + 1 s c ^ = c i 1 + ( 2 ( n + 1 ) − s ) − ( 2 n − s ) = 1 + 2 = 3. Kyon: push 2 units potential add karta hai (future ke liye bachata hai) 1 real write ki cost par.
Resizing push (table full: n = s n s → 2 s n → n + 1
Actual cost c i = n + 1 n
Pehle: Φ = 2 n − s = 2 n − n = n
Baad: Φ = 2 ( n + 1 ) − 2 s = 2 ( n + 1 ) − 2 n = 2 c ^ = ( n + 1 ) + ( 2 − n ) = 3. Yeh punchline kyon hai: badi real cost n + 1 n − 2 cancel hoti hai. Stored energy copy ke liye pay karta hai. c ^ = O ( 1 )
Recall Feynman: ek 12-saal ke bacche ko samjhaoEk piggy bank imagine karo. Har baar jab tum ek chhota kaam karte ho, tum 3 coins daalte ho par kaam sirf 1 coin ka "effort" leta hai. Extra 2 coins pile up hote hain. Kabhi kabhi ek BAHUT BADA kaam aata hai (poora kamra saaf karna). Rone ki jagah, tum piggy bank tod dete ho — aur surprise, tumne exactly itne coins bachaye hain jo usse pay karne ke liye kafi hain! Toh chahe ek kaam bahut bada lagta tha, average par har kaam ne tumhe sirf 3 coins cost kiye. Yahi averaged-but-guaranteed price amortized cost hai, aur piggy bank potential function hai.
Mnemonic Teen methods yaad karo"A-A-P" → A ggregate (sab Add karo, divide karo), A ccounting (bank Account / credit), P otential (Physics energy Φ "Actual plus Delta-Phi" — c ^ = c + ΔΦ
Amortized cost kis tarah ka average hai — inputs par ya sequence par guaranteed? Kisi bhi sequence of operations par guaranteed worst-case; koi probability/randomness NAHI hai.
Aggregate method ek line mein m T ( m ) = T ( m ) / m
Dynamic array push O ( 1 ) O ( n ) Copies geometrically rarely hoti hain; total copy work = 1 + 2 + ⋯ + 2 k < 2 m T ( m ) < 3 m
Accounting method validity condition Total stored credit ∑ ( c ^ i − c i ) ≥ 0
Potential method ki master equation c ^ i = c i + Φ ( D i ) − Φ ( D i − 1 )
Potential method valid upper bound kyon deta hai? Telescoping: ∑ c ^ i = ∑ c i + Φ ( D m ) − Φ ( D 0 ) Φ ( D m ) ≥ Φ ( D 0 ) ∑ c ^ i ≥ ∑ c i
Ek achhe potential function ki do requirements Φ ( D 0 ) = 0 Φ ( D i ) ≥ 0 i
Table doubling ke liye potential function Φ = 2 n − s c ^ = 3
Binary counter increment ki amortized cost O ( 1 ) 1 → 0
Amortized vs average-case complexity ka farq Amortized = ek sequence par deterministic guarantee; average-case = inputs ke random distribution par expectation.
Dynamic Arrays / Table Doubling — canonical amortized example.Big-O, Big-Omega, Big-Theta — amortized bounds abhi bhi asymptotic notation mein express hote hain.Disjoint Set Union (Union-Find) — path compression + union by rank potential ke zariye analyze kiya gaya.Splay Trees — O ( log n ) Fibonacci Heaps — decrease-key O ( 1 ) Geometric Series — aggregate method ke peeche ka summation engine.
Average-case with randomness
Sum c-hat >= Sum actual cost
