Intuition The big picture (WHY this exists)Some operations are occasionally expensive but usually cheap . If you bound them by their worst single case , you lie about the truth. Example: a dynamic array's push is O ( 1 ) O(1) O ( 1 ) O ( n ) O(n) O ( n ) over a whole sequence of operations, what is the average cost per operation — guaranteed, not probabilistic?
Key word: guaranteed . Amortized ≠ \neq = no randomness . We promise that any sequence of m m m m ⋅ ( amortized cost ) m \cdot (\text{amortized cost}) m ⋅ ( amortized cost )
Definition Amortized costGiven a sequence of m m m total actual cost T ( m ) T(m) T ( m ) amortized cost per operation is any value c ^ \hat{c} c ^ ∑ i = 1 m c ^ i ≥ ∑ i = 1 m c i (actual cost) \sum_{i=1}^{m} \hat{c}_i \;\ge\; \sum_{i=1}^{m} c_i \quad \text{(actual cost)} ∑ i = 1 m c ^ i ≥ ∑ i = 1 m c i (actual cost) c ^ = 1 m ∑ c ^ i \hat{c} = \frac{1}{m}\sum \hat{c}_i c ^ = m 1 ∑ c ^ i honest because the left side upper-bounds the real total work.
There are three methods to find c ^ \hat{c} c ^ how you account .
Compute the total cost T ( m ) T(m) T ( m ) m m m = T ( m ) / m = T(m)/m = T ( m ) / m same amortized cost. Simplest to think about, weakest when operations differ.
Worked example Dynamic array (table doubling),m m m HOW: Start with capacity 1. When full, allocate double and copy.
Cheap part: each push writes 1 element ⇒ \Rightarrow ⇒ m m m
Expensive part (copies): we copy when size hits 1 , 2 , 4 , 8 , … 1, 2, 4, 8, \dots 1 , 2 , 4 , 8 , … 1 + 2 + 4 + ⋯ + 2 k 1+2+4+\dots+2^{k} 1 + 2 + 4 + ⋯ + 2 k 2 k ≤ m 2^k \le m 2 k ≤ m
Why this step? The copy sizes form a geometric series. The crucial fact:
1 + 2 + 4 + ⋯ + 2 k = 2 k + 1 − 1 < 2 m . 1+2+4+\dots+2^k = 2^{k+1}-1 < 2m. 1 + 2 + 4 + ⋯ + 2 k = 2 k + 1 − 1 < 2 m . Total: T ( m ) ≤ m + 2 m = 3 m T(m) \le m + 2m = 3m T ( m ) ≤ m + 2 m = 3 m Amortized: c ^ = T ( m ) / m ≤ 3 = = = O ( 1 ) = = \hat{c} = T(m)/m \le 3 = ==O(1)== c ^ = T ( m ) / m ≤ 3 === O ( 1 ) ==
Common mistake Steel-man: "doubling copiesn n n O ( n ) O(n) O ( n ) Why it feels right: the single expensive push really does copy n n n The fix: that O ( n ) O(n) O ( n ) once every n n n . The expensive events are rare and geometrically spaced , so the copies sum to < 2 m <2m < 2 m m ⋅ n m\cdot n m ⋅ n
Charge each operation an amortized cost c ^ \hat c c ^ more than its real cost. The surplus is stored as credit on data-structure elements. Later, expensive operations spend stored credit instead of charging the user. Rule that makes it valid:
total credit = ∑ ( c ^ i − c i ) ≥ 0 at all times. \text{total credit} = \sum(\hat c_i - c_i) \ge 0 \quad \text{at all times.} total credit = ∑ ( c ^ i − c i ) ≥ 0 at all times. ∑ c ^ ≥ ∑ c \sum \hat c \ge \sum c ∑ c ^ ≥ ∑ c
Worked example Dynamic array, accounting styleHOW: Charge c ^ = 3 \hat c = 3 c ^ = 3 1 1 1
Spend $1 to place the new element.
Store $1 on the new element (to pay to move itself later).
Store $1 on an older element that has no credit yet.
Why this step? When the array doubles from n n n 2 n 2n 2 n n n n n n n prepaid — credit never goes negative.
Amortized: c ^ = 3 = O ( 1 ) \hat c = 3 = O(1) c ^ = 3 = O ( 1 )
Worked example Binary counter increment (k-bit)Cost of increment = number of bits flipped.
Accounting: charge $2 per increment. Setting a bit 0 → 1 0\to1 0 → 1 1 and stores \ 1 on that bit. When a bit flips 1 → 0 1\to0 1 → 0 1 ∗ ∗ . ∗ ∗ W h y v a l i d : ∗ ∗ e v e r y 1**.
**Why valid:** every 1 ∗ ∗ . ∗ ∗ W h y v a l i d : ∗ ∗ e v er y bit always carries exactly \ 1 of credit, so all the cascading carries are prepaid. Amortized cost of increment = = = O ( 1 ) = = = ==O(1)== === O ( 1 ) == k k k
Intuition WHAT (the most powerful, most reusable)Define a potential function Φ ( D ) \Phi(D) Φ ( D ) D D D plus the change in potential :
c ^ i = c i + Φ ( D i ) − Φ ( D i − 1 ) \boxed{\hat c_i = c_i + \Phi(D_i) - \Phi(D_{i-1})} c ^ i = c i + Φ ( D i ) − Φ ( D i − 1 ) WHY this works (derive the telescoping):
∑ i = 1 m c ^ i = ∑ i = 1 m c i + ( Φ ( D m ) − Φ ( D 0 ) ) . \sum_{i=1}^m \hat c_i = \sum_{i=1}^m c_i + \big(\Phi(D_m) - \Phi(D_0)\big). ∑ i = 1 m c ^ i = ∑ i = 1 m c i + ( Φ ( D m ) − Φ ( D 0 ) ) . Φ ( D m ) ≥ Φ ( D 0 ) \Phi(D_m) \ge \Phi(D_0) Φ ( D m ) ≥ Φ ( D 0 ) Φ ≥ 0 \Phi\ge0 Φ ≥ 0 Φ ( D 0 ) = 0 \Phi(D_0)=0 Φ ( D 0 ) = 0 ∑ c ^ i ≥ ∑ c i . \sum \hat c_i \ge \sum c_i. ∑ c ^ i ≥ ∑ c i .
Worked example Dynamic array via potential — deriveΦ \Phi Φ n n n s s s Φ \Phi Φ Choose Φ = 2 n − s \Phi = 2n - s Φ = 2 n − s n ≥ s / 2 n \ge s/2 n ≥ s /2 ≥ 0 \ge 0 ≥ 0 n ≥ s / 2 ⇒ 2 n ≥ s n\ge s/2 \Rightarrow 2n\ge s n ≥ s /2 ⇒ 2 n ≥ s
Non-resizing push (n → n + 1 n \to n+1 n → n + 1 s s s c ^ = 1 ⏟ c i + ( 2 ( n + 1 ) − s ) − ( 2 n − s ) = 1 + 2 = 3. \hat c = \underbrace{1}_{c_i} + \big(2(n+1)-s\big)-\big(2n-s\big) = 1 + 2 = 3. c ^ = c i 1 + ( 2 ( n + 1 ) − s ) − ( 2 n − s ) = 1 + 2 = 3. Why: push adds 2 units of potential (saving for the future) at cost of 1 real write.
Resizing push (table full: n = s n=s n = s n n n s → 2 s s\to 2s s → 2 s n → n + 1 n\to n+1 n → n + 1
Actual cost c i = n + 1 c_i = n+1 c i = n + 1 n n n
Before: Φ = 2 n − s = 2 n − n = n \Phi = 2n - s = 2n - n = n Φ = 2 n − s = 2 n − n = n
After: Φ = 2 ( n + 1 ) − 2 s = 2 ( n + 1 ) − 2 n = 2 \Phi = 2(n+1) - 2s = 2(n+1)-2n = 2 Φ = 2 ( n + 1 ) − 2 s = 2 ( n + 1 ) − 2 n = 2 c ^ = ( n + 1 ) + ( 2 − n ) = 3. \hat c = (n+1) + (2 - n) = 3. c ^ = ( n + 1 ) + ( 2 − n ) = 3. Why this is the punchline: the big real cost n + 1 n{+}1 n + 1 cancelled by the potential dropping by n − 2 n{-}2 n − 2 c ^ = O ( 1 ) \hat c = O(1) c ^ = O ( 1 )
Recall Feynman: explain to a 12-year-oldImagine a piggy bank. Every time you do a small chore you put in 3 coins but the chore only "costs" 1 coin of effort. The extra 2 coins pile up. Once in a while a HUGE chore appears (cleaning the whole room). Instead of crying, you smash the piggy bank — and surprise, you saved exactly enough coins to pay for it! So even though one chore looked giant, on average every chore only ever cost you 3 coins. That averaged-but-guaranteed price is the amortized cost , and the piggy bank is the potential function .
Mnemonic Remember the three methods"A-A-P" → A ggregate (Add all, divide), A ccounting (bank Account / credit), P otential (Physics energy Φ \Phi Φ "Actual plus Delta-Phi" — c ^ = c + Δ Φ \hat c = c + \Delta\Phi c ^ = c + ΔΦ
Amortized cost is which kind of average — over inputs or guaranteed over a sequence? Guaranteed worst-case over any sequence of operations; there is NO probability/randomness involved.
Aggregate method in one line Compute total cost
T ( m ) T(m) T ( m ) of
m m m ops directly, then amortized cost
= T ( m ) / m = T(m)/m = T ( m ) / m (same for every op).
Why is a dynamic array push O ( 1 ) O(1) O ( 1 ) O ( n ) O(n) O ( n ) Copies happen geometrically rarely; total copy work
= 1 + 2 + ⋯ + 2 k < 2 m =1+2+\dots+2^k<2m = 1 + 2 + ⋯ + 2 k < 2 m , so total
T ( m ) < 3 m T(m)<3m T ( m ) < 3 m .
Accounting method validity condition Total stored credit
∑ ( c ^ i − c i ) \sum(\hat c_i-c_i) ∑ ( c ^ i − c i ) must stay
≥ 0 \ge 0 ≥ 0 at all times (bank never goes negative).
Master equation of the potential method c ^ i = c i + Φ ( D i ) − Φ ( D i − 1 ) \hat c_i = c_i + \Phi(D_i)-\Phi(D_{i-1}) c ^ i = c i + Φ ( D i ) − Φ ( D i − 1 ) (actual cost plus change in potential).
Why does the potential method give a valid upper bound? Telescoping:
∑ c ^ i = ∑ c i + Φ ( D m ) − Φ ( D 0 ) \sum\hat c_i=\sum c_i+\Phi(D_m)-\Phi(D_0) ∑ c ^ i = ∑ c i + Φ ( D m ) − Φ ( D 0 ) ; if
Φ ( D m ) ≥ Φ ( D 0 ) \Phi(D_m)\ge\Phi(D_0) Φ ( D m ) ≥ Φ ( D 0 ) then
∑ c ^ i ≥ ∑ c i \sum\hat c_i\ge\sum c_i ∑ c ^ i ≥ ∑ c i .
Two requirements for a good potential function Φ ( D 0 ) = 0 \Phi(D_0)=0 Φ ( D 0 ) = 0 and
Φ ( D i ) ≥ 0 \Phi(D_i)\ge0 Φ ( D i ) ≥ 0 for all
i i i .
Potential function used for table doubling Φ = 2 n − s \Phi=2n-s Φ = 2 n − s (n = #elements, s = capacity), giving
c ^ = 3 \hat c=3 c ^ = 3 per push.
Amortized cost of incrementing a binary counter O ( 1 ) O(1) O ( 1 ) — charge $2: \backslash
1 to set a bit, \ 1 stored on it to pay its future
1 → 0 1\to0 1 → 0 flip.
Difference: amortized vs average-case complexity Amortized = deterministic guarantee over a sequence; average-case = expectation over a random distribution of inputs.
Dynamic Arrays / Table Doubling — the canonical amortized example.Big-O, Big-Omega, Big-Theta — amortized bounds are still expressed in asymptotic notation.Disjoint Set Union (Union-Find) — path compression + union by rank analyzed via potential.Splay Trees — O ( log n ) O(\log n) O ( log n ) Fibonacci Heaps — decrease-key O ( 1 ) O(1) O ( 1 ) Geometric Series — the summation engine behind the aggregate method.
Average-case with randomness
Sum c-hat >= Sum actual cost
Intuition Hinglish mein samjhoDekho, amortized analysis ka basic idea simple hai: kuch operations kabhi-kabhi bahut mehenge hote hain, par mostly sasta. Jaise dynamic array me push — normally O ( 1 ) O(1) O ( 1 ) O ( n ) O(n) O ( n ) O ( n ) O(n) O ( n ) guarantee hota hai, koi probability nahi (yahi average-case se difference hai).
Teen methods hain, yaad rakho A-A-P . Aggregate : total cost T ( m ) T(m) T ( m ) m m m 1 + 2 + 4 + ⋯ < 2 m 1+2+4+\dots < 2m 1 + 2 + 4 + ⋯ < 2 m < 3 m < 3m < 3 m ≤ 3 = O ( 1 ) \le 3 = O(1) ≤ 3 = O ( 1 ) Accounting (banker's): har push pe $3 \text{ charge karo jabki real cost }1 hai. Extra \ 2 ko credit ki tarah elements pe store karo — jab copy ka time aaye, wo stored credit se pay ho jaata hai, user se extra nahi maangte.
Potential method sabse powerful aur reusable hai. Ek function Φ \Phi Φ c ^ = c + Δ Φ \hat c = c + \Delta\Phi c ^ = c + ΔΦ Φ \Phi Φ Φ \Phi Φ c ^ \hat c c ^ Φ = 2 n − s \Phi = 2n - s Φ = 2 n − s c ^ = 3 \hat c = 3 c ^ = 3 O ( 1 ) O(1) O ( 1 )
Ye matter karta hai kyunki real interviews aur real systems me (DSU, splay trees, Fibonacci heaps) tum worst-single-case se bound loge to bahut loose answer milega. Amortized se tight aur honest bound milta hai — "average per operation, guaranteed". Piggy bank wala example yaad rakho: chhote chores me coins jama karo, bada chore aaye to gullak phod ke pay kar do.
