Amortized analysis — aggregate, accounting আর potential

১ · প্রতিটি কাজের worst case কেন অতিরিক্ত হতাশাবাদী

পর্ব ১০-এ আপনি দেখেছেন, dynamic array (C++-এর std::vector, Python-এর list) জায়গা ফুরালে নতুন বড় ব্লক নিয়ে সব উপাদান কপি করে। তাহলে একটি push_back সবচেয়ে খারাপে Θ(n). এখন সরল হিসাব: n টি push, প্রতিটির worst case O(n), তাই মোট O(n²). হিসাবটি ভুল নয় — upper bound হিসেবে সত্য। কিন্তু অনেক বেশি হতাশাবাদী। বাস্তবে দশ লাখ push-এ মোট কপি মাত্র প্রায় দশ লাখ, দশ লাখ গুণ দশ লাখ নয়।

ভুলটি কোথায়? আমরা ধরে নিয়েছি প্রতিটি কাজ একসাথে সবচেয়ে খারাপ হতে পারে। অথচ দামি কাজটি (কপি) ঘটলে capacity দ্বিগুণ হয়, আর তার পরের অনেকগুলো push নিশ্চিতভাবে সস্তা। দামি কাজ নিজেই পরের সস্তা কাজের জায়গা বানিয়ে দেয়। কাজগুলো স্বাধীন নয় — তারা একটি ক্রমে আসে, আর ডেটা স্ট্রাকচারের অবস্থা তাদের জুড়ে রাখে।

শব্দটিও এসেছে অর্থনীতি থেকে: ঋণ amortize করা মানে বড় অঙ্কটিকে সমান কিস্তিতে ভাগ করে শোধ করা — যেমন বাড়ি বা মোটরসাইকেলের মাসিক কিস্তি। Amortized analysis-এ আমরা কয়েকটি দামি কাজের খরচ সব কাজের ওপর কিস্তিতে ভাগ করে দিই। সংজ্ঞা:

Amortized বনাম average case — কোনো সম্ভাবনা নেই!

এখানে সবচেয়ে প্রচলিত বিভ্রান্তি: “amortized O(1) মানে গড়ে O(1), তাই ভাগ্য খারাপ হলে ধীর হতে পারে”. না। পর্ব ৫-এর average case ইনপুটের একটি সম্ভাবনা-বণ্টন ধরে নেয় — ইনপুট এলোমেলো হলে প্রত্যাশিত খরচ। Amortized সীমা কোনো বণ্টন ধরে না: প্রতিপক্ষ যত খারাপ ক্রমই বাছুক, পুরো ক্রমের মোট খরচ সীমার মধ্যে থাকবেই। এটি worst case-এরই একটি রূপ — শুধু একটি কাজের নয়, পুরো ক্রমের।

দুটি একসাথেও আসতে পারে — যেমন hash table-এর insert “expected amortized O(1)”: rehashing-এর খরচ amortized, আর collision-এর খরচ hash function-এর এলোমেলোতার ওপর expected (পর্ব ৩২). তবে এই পর্বের সব ফল সম্ভাবনা ছাড়া, নিশ্চিত।

২ · তিনটি উদাহরণ — dynamic array, binary counter আর multipop

পুরো পর্বে আমরা একই তিনটি ডেটা স্ট্রাকচার তিন পদ্ধতিতে বিশ্লেষণ করব, যাতে পদ্ধতিগুলোর পার্থক্য স্পষ্ট হয়। প্রতিটিতে খরচের একক ঠিক করা দরকার।

প্রথমটি দিয়ে শুরু করুন। খালি array (capacity ১) থেকে নয়টি push — প্রতিটির খরচ আর মোট খরচের গড় দেখুন:

দ্বিতীয় উদাহরণটি binary counter — গাড়ির কিলোমিটার মিটারের মতো, শুধু দশমিকের বদলে দুই ভিত্তিতে। মিটার ০৯৯৯ থেকে ১০০০ হলে চারটি চাকা ঘোরে, কিন্তু বেশিরভাগ সময় শুধু শেষ চাকাটি। k বিটের counter-এ একটি increment সবচেয়ে খারাপে k টি flip, তাই সরল হিসাবে n increment-এ O(nk). আসলে কত?

তৃতীয় উদাহরণ multipop. একটি multipop(k) একাই n টি pop করতে পারে, তাই সরল হিসাবে n কাজে O(n²). কিন্তু একটু ভাবুন: যে উপাদান কখনো push হয়নি, তাকে pop করা যায় না। প্রতিটি উপাদান একবার ঢোকে, সর্বোচ্চ একবার বের হয়। পরের তিন অংশে এই তিনটি অন্তর্দৃষ্টিকে তিনটি আনুষ্ঠানিক পদ্ধতিতে রূপ দেব।

৩ · Aggregate method — মোট যোগ করে ভাগ

সবচেয়ে সরাসরি পদ্ধতি: n টি কাজের যেকোনো ক্রমের মোট খরচ T(n)-এর একটি সীমা প্রমাণ করুন, তারপর n দিয়ে ভাগ। একে বলে aggregate method. এখানে সব কাজের amortized খরচ একই — T(n)/n.

Multipop. pop (multipop-এর ভেতরেরগুলো সহ) কতবার হতে পারে? প্রতিটি pop একটি আগে push হওয়া উপাদান সরায়, তাই মোট pop ≤ মোট push ≤ n. সব কাজ মিলে মোট খরচ ≤ 2n = O(n), প্রতি কাজে amortized O(1). লক্ষ করুন, যুক্তিটি কোনো একটি multipop-এর আকার নিয়ে কিছু বলে না — শুধু পুরো ক্রমের মোট নিয়ে।

Binary counter. A[0] প্রতিটি increment-এ উল্টায়: n বার। A[1] প্রতি দ্বিতীয়টিতে: ⌊n/2⌋ বার। সাধারণভাবে A[i] উল্টায় ⌊n/2ⁱ⌋ বার। তাই মোট flip

অর্থাৎ k যত বড়ই হোক, প্রতি increment-এ amortized O(1) — ঠিক ২-এর কম flip. এটি পর্ব ৬-এর geometric series.

Dynamic array, growth factor ২. n টি push-এ কপি হয় শুধু size যখন ১, ২, ৪, …, 2^j (যেখানে 2^j < n). মোট কপি 1 + 2 + … + 2^j = 2^j+1 − 1 < 2n. সাথে n টি লেখা — মোট < 3n. তাই push_back amortized O(1), যদিও একটি push Θ(n).

যেকোনো growth factor g > 1 চলে, কিন্তু ধ্রুবক যোগ চলে না

Growth factor g হলে কপির আকারগুলো একটি গুণোত্তর ধারা, যার শেষ পদ < n: মোট < n · (1 + 1/g + 1/g² + …) = n · g/(g − 1). g = 2-এ < 2n, g = 1.5-এ < 3n — দুটোই Θ(n), পার্থক্য শুধু ধ্রুবকে (১.৫ কম মেমরি নষ্ট করে, কিন্তু বেশি কপি করে; বিস্তারিত পর্ব ১০-এ)। g যত ১-এর কাছে যায়, g/(g − 1) তত বড় — তবু ধ্রুবক।

এবার “প্রতিবার ১০০টি ঘর বাড়াও” ভাবুন — শুনতে মিতব্যয়ী। কপির আকার 100, 200, 300, …, প্রায় n পর্যন্ত: মোট ≈ 100 · (1 + 2 + … + n/100) ≈ n²/200. তাই n push-এ Θ(n²), প্রতি push-এ amortized Θ(n). ধ্রুবক c যত বড়ই হোক, n²/(2c) শেষে জিতবেই। নিচের প্রোগ্রাম তিনটি নিয়ম পাশাপাশি চালিয়ে মোট কপি গোনে:

#include <algorithm>
#include <cstdio>
#include <initializer_list>
#include <string>
#include <utility>
using namespace std;

// n times push_back into an empty dynamic array; returns {resizes, copies}
pair<long long, long long> simulate(long long n, const string& rule) {
    long long size = 0, cap = 1, copies = 0, resizes = 0;
    for (long long k = 0; k < n; ++k) {
        if (size == cap) {                      // full: allocate bigger, copy all
            copies += size;
            ++resizes;
            if (rule == "x2")        cap = 2 * cap;
            else if (rule == "x1.5") cap = max(cap + 1, cap + cap / 2);
            else                     cap = cap + 100;   // "+100": constant growth
        }
        ++size;                                 // write the new element
    }
    return {resizes, copies};
}

int main() {
    printf("rule       n   resizes        copies  copies/n\n");
    for (long long n : {1000LL, 100000LL, 1000000LL})
        for (const char* rule : {"x2", "x1.5", "+100"}) {
            auto [r, c] = simulate(n, rule);
            printf("%4s %8lld %9lld %13lld %9.2f\n", rule, n, r, c, double(c) / n);
        }
}

rule       n   resizes        copies  copies/n
  x2     1000        10          1023      1.02
x1.5     1000        17          2137      2.14
+100     1000        10          4510      4.51
  x2   100000        17        131071      1.31
x1.5   100000        29        276521      2.77
+100   100000      1000      49951000    499.51
  x2  1000000        20       1048575      1.05
x1.5  1000000        34       2099753      2.10
+100  1000000     10000    4999510000   4999.51

def simulate(n, rule):
    size, cap, copies, resizes = 0, 1, 0, 0
    for _ in range(n):                      # n times push_back
        if size == cap:                     # full: allocate bigger, copy all
            copies += size
            resizes += 1
            if rule == "x2":
                cap = 2 * cap
            elif rule == "x1.5":
                cap = max(cap + 1, cap + cap // 2)
            else:
                cap = cap + 100             # "+100": constant growth
        size += 1                           # write the new element
    return resizes, copies

print("rule       n   resizes        copies  copies/n")
for n in (1000, 100000, 1000000):
    for rule in ("x2", "x1.5", "+100"):
        r, c = simulate(n, rule)
        print(f"{rule:>4} {n:>8} {r:>9} {c:>13} {c / n:>9.2f}")

rule       n   resizes        copies  copies/n
  x2     1000        10          1023      1.02
x1.5     1000        17          2137      2.14
+100     1000        10          4510      4.51
  x2   100000        17        131071      1.31
x1.5   100000        29        276521      2.77
+100   100000      1000      49951000    499.51
  x2  1000000        20       1048575      1.05
x1.5  1000000        34       2099753      2.10
+100  1000000     10000    4999510000   4999.51

৪ · Accounting method — সস্তা কাজে কয়েন জমানো

Aggregate পদ্ধতি সব কাজকে একই amortized খরচ দেয়। কিন্তু কখনো আলাদা আলাদা দাম দিলে যুক্তি সহজ হয়: push-এর দাম ২, pop-এর দাম ০. Accounting method-এ প্রতিটি কাজের একটি amortized দাম ĉ ঠিক করা হয়। আসল খরচের চেয়ে বেশি নিলে বাড়তিটা credit (কয়েন) হিসেবে ডেটা স্ট্রাকচারের নির্দিষ্ট অংশের গায়ে জমা থাকে; কম নিলে ঘাটতি সেই জমা থেকে মেটে — ঠিক ঈদের মাটির ব্যাংক।

Multipop. push-এর দাম ২: ১ দিয়ে push-এর খরচ মেটে, বাকি ১ কয়েন উপাদানটির গায়ে থাকে। pop আর multipop-এর দাম ০: প্রতিটি সরানো উপাদান নিজের কয়েন দিয়ে নিজের pop মেটায়। Invariant: stack-এর প্রতিটি উপাদানের গায়ে ঠিক ১ কয়েন, তাই ব্যাংক = stack-এর আকার ≥ ০. ফল: n কাজে মোট ≤ 2n.

Binary counter. কোনো বিটকে 0 থেকে 1 করার দাম ২: ১ দিয়ে flip, ১ কয়েন সেই বিটের গায়ে। 1 থেকে 0 করার দাম ০ — বিটের গায়ের কয়েনই মেটায়। Invariant: প্রতিটি 1-বিটের গায়ে ১ কয়েন। একটি INCREMENT ঠিক একটি বিটকে 0 → 1 করে (counter উপচে না পড়লে), তাই তার দাম ২; সামনের সব 1 → 0 বিনামূল্যে। n increment-এ মোট flip ≤ 2n — অংশ ৩-এর ফলই, অন্য পথে।

Dynamic array. প্রতিটি push-এর দাম ৩: ১ দিয়ে নিজের লেখা, ১ কয়েন নিজের গায়ে (পরের resize-এ নিজের কপির জন্য), আর ১ কয়েন আগের অর্ধেকের এমন একটি উপাদানের গায়ে, যার কয়েন আগের resize-এ খরচ হয়ে গেছে। Capacity c থেকে 2c হওয়ার মুহূর্তে c টি পুরোনো উপাদান কপি হয়ে কয়েনহীন। এরপর যে c টি push (resize ঘটানোটি সহ) array-কে 2c পর্যন্ত ভরে, তারা মোট 2c কয়েন রাখে — পরের resize-এ ঠিক 2c টি উপাদান কপি করার জন্য যথেষ্ট। তাই ব্যাংক কখনো ঋণাত্মক নয়, আর push-এর amortized খরচ ৩. অংশ ২-এর প্রথম ডায়াগ্রামে “মোট খরচ ÷ push” কখনো ৩ ছাড়ায়নি — এই কারণেই।

৫ · Potential method — জমানো শক্তি Φ

Accounting-এ কয়েন থাকে নির্দিষ্ট উপাদানের গায়ে। জটিল ডেটা স্ট্রাকচারে কোন কয়েন কার গায়ে, তা মনে রাখা কঠিন। Potential method বলে: আলাদা কয়েন নয়, পুরো ডেটা স্ট্রাকচারের অবস্থাকে একটি সংখ্যা দিন — potential function Φ(D). পদার্থবিজ্ঞানের স্থিতিশক্তির মতো: ওপরে তোলা পাথরে শক্তি জমা থাকে, পড়ার সময় সেই শক্তি কাজ করে। সস্তা কাজে Φ বাড়ে (শক্তি জমে), দামি কাজে Φ কমে (জমা শক্তি খরচ হয়)।

এখানে c_i হলো i-তম কাজের আসল খরচ, D_i সেই কাজের পরের অবস্থা। সব যোগ করলে মাঝের Φ-গুলো কাটাকাটি হয়ে যায় — একে বলে telescoping sum:

তাই যদি সবসময় Φ(D_i) ≥ Φ(D₀) হয় (সাধারণত Φ(D₀) = 0 আর Φ ≥ 0), তবে Σ c_i ≤ Σ ĉ_i — amortized খরচগুলো আসল মোটের সীমা। কাজ হলো ভালো একটি Φ খোঁজা: দামি কাজে Φ যেন ঠিক ততটা কমে, যতটা বাড়তি খরচ হলো।

• Multipop: Φ = stack-এর আকার। push: c = 1, ΔΦ = +1 → ĉ = 2. multipop(k) যা k′ টি সরায়: c = k′, ΔΦ = −k′ → ĉ = 0.
• Binary counter: Φ = counter-এ 1-এর সংখ্যা। যে increment t টি 1-কে 0 করে আর একটি 0-কে 1: c = t + 1, ΔΦ = 1 − t → ĉ = 2. (অংশ ২-এর ডায়াগ্রামের শেষ সারিটি এই Φ.)
• Dynamic array: Φ = 2·size − capacity. Resize ছাড়া: c = 1, ΔΦ = +2 → ĉ = 3. size = capacity = m অবস্থায় resize: c = m + 1, Φ m থেকে 2(m + 1) − 2m = 2, ΔΦ = 2 − m → ĉ = 3.

Φ = 2·size − capacity-র অর্থ: “পরের resize-এর আগে কত কপি জমা করে রাখতে হবে”. Resize-এর ঠিক পরে array অর্ধেক ভরা, Φ প্রায় ০ — শক্তি সব খরচ হয়েছে। Array ভরে উঠতে উঠতে Φ বেড়ে capacity-তে পৌঁছায় — ঠিক পরের কপির খরচ। Accounting-এর কয়েনগুলোর মোট সংখ্যাই আসলে Φ; potential method সেই যোগফলকে উপাদান-নিরপেক্ষ একটি সূত্রে লেখে।

Pseudocode — the potential-method proof recipe

1. Choose Phi(D) from the state of the structure (size, number of 1s, ...).
2. Check Phi(D0) = 0 and Phi(D) >= 0 for every reachable state D.
3. For every operation type, compute  amortized = actual + Phi(after) - Phi(before).
4. Bound each amortized cost (cheap case AND expensive case).
5. Conclude: total actual <= sum of amortized bounds   (telescoping).

৬ · Array ছোট করা — ¼ নিয়ম আর thrashing

এখন pop-ও আছে, আর আমরা চাই অনেক উপাদান মুছে গেলে array মেমরি ফেরত দিক। সহজ চিন্তা: “বড় করি ভরা হলে দ্বিগুণ, তাহলে ছোট করি অর্ধেক খালি হলে অর্ধেক”. শুনতে প্রতিসম, কিন্তু ফাঁদ আছে। ধরুন size = capacity = n. একটি push: দ্বিগুণ, n কপি; এখন ঠিক অর্ধেকের একটু বেশি ভরা। একটি pop: ঠিক অর্ধেক — ছোট করা, আবার n কপি, আবার পুরো ভরা। push, pop, push, pop … প্রতিটি কাজ Θ(n). একে বলে thrashing.

সমাধান: ছোট করুন যখন array ¼ ভরা, আর ছোট করে capacity অর্ধেক করুন। তখন বড় বা ছোট করার ঠিক পরে array সবসময় অর্ধেক ভরা — পরের resize-এর আগে অন্তত capacity/৪ টি কাজ লাগবে, যারা কপির খরচ জমাবে। Potential দিয়ে প্রমাণ (α = size/capacity):

দুই অংশই অর্ধেক ভরা অবস্থায় ০, আর অর্ধেক থেকে যেকোনো দিকে সরলে বাড়ে। ভরা অবস্থায় Φ = capacity, ¼ ভরা অবস্থায় Φ = capacity/4 = size — দুই ক্ষেত্রেই ঠিক কপির খরচের সমান শক্তি জমা। হিসাব করলে প্রতিটি push আর pop-এর amortized খরচ ধ্রুবক (৩-এর মধ্যে) — CLRS-এর amortized analysis অধ্যায়ে পুরো হিসাবটি আছে। জায়গাও Θ(size): capacity কখনো size-এর ৪ গুণের বেশি নয় (খালি অবস্থা বাদে)।

৭ · দুই stack দিয়ে queue, আর পরিচিত মুখগুলো

ইন্টারভিউর একটি প্রিয় প্রশ্ন: শুধু দুটি stack দিয়ে একটি queue বানান। কৌশল: inbox-এ সব enqueue; dequeue-এর সময় outbox খালি হলে inbox-এর সব উপাদান একে একে outbox-এ ঢালুন — ক্রম উল্টে যায়, তাই সবচেয়ে পুরোনোটি এখন outbox-এর ওপরে। তারপর outbox থেকে pop. এটিই two-stack queue. ব্যাংকের লাইনের উপমায়: নতুন লোকেরা পেছনের ঘরে বসে; সামনের কাউন্টার ফাঁকা হলে পুরো ঘরের লোকদের একসাথে উল্টো ক্রমে সামনে সাজানো হয়।

একটি dequeue-তে inbox-এর n টি উপাদান সরতে পারে — Θ(n). কিন্তু প্রতিটি উপাদান জীবনে ঠিক একবারই inbox থেকে outbox-এ যায়। খরচের একক = একটি stack push বা pop. Accounting: enqueue-এর দাম ৩ (১ নিজের push, ২ কয়েন ভবিষ্যতের “inbox থেকে pop + outbox-এ push”-এর জন্য), dequeue-এর দাম ১. Potential: Φ = 2·|inbox|; enqueue: ১ + ২ = ৩; সাধারণ dequeue: ১ + ০ = ১; k টি ঢালার dequeue: (1 + 2k) − 2k = ১. তাই n কাজে মোট ≤ 3n.

নিচের প্রোগ্রাম দুটি দাবি গুনে দেখে: binary counter-এর মোট flip বনাম 2n, আর ৩টি enqueue + ২টি dequeue-এর একটি ধাঁচ ১০০০ বার (তারপর সব খালি) চালিয়ে two-stack queue-র মোট stack-ধাপ আর সবচেয়ে দামি একক কাজ।

#include <algorithm>
#include <cstdio>
#include <initializer_list>
#include <vector>
using namespace std;
long long counterFlips(long long n, int bits = 32) {
    vector<int> a(bits, 0);                     // a[0] = lowest bit
    long long flips = 0;
    for (long long k = 0; k < n; ++k) {         // n times INCREMENT
        int i = 0;
        while (i < bits && a[i] == 1) { a[i] = 0; ++flips; ++i; }   // trailing 1s -> 0
        if (i < bits) { a[i] = 1; ++flips; }    // first 0 -> 1
    }
    return flips;
}
vector<int> inbox, outbox;                      // queue built from two stacks
long long ops = 0, cost = 0, worst = 0;
void enqueue(int x) { inbox.push_back(x); ++ops; ++cost; worst = max(worst, 1LL); }
void dequeue() {
    long long c = 1;
    if (outbox.empty())                         // refill: move everything, reversing order
        while (!inbox.empty()) { outbox.push_back(inbox.back()); inbox.pop_back(); c += 2; }
    outbox.pop_back(); ++ops; cost += c; worst = max(worst, c);
}

int main() {
    printf("binary counter:   n   flips  2n-bound  flips/n\n");
    for (long long n : {8LL, 16LL, 1000LL, 1000000LL}) {
        long long f = counterFlips(n);
        printf("%21lld %7lld %9lld %8.3f\n", n, f, 2 * n, double(f) / n);
    }
    for (int i = 0; i < 1000; ++i) {            // pattern: 3 enqueues, then 2 dequeues
        for (int j = 0; j < 3; ++j) enqueue(3 * i + j);
        dequeue(); dequeue();
    }
    while (!inbox.empty() || !outbox.empty()) dequeue();
    printf("two-stack queue: ops = %lld, stack steps = %lld, worst single op = %lld, steps/op = %.2f\n",
           ops, cost, worst, double(cost) / ops);
}

binary counter:   n   flips  2n-bound  flips/n
                    8      15        16    1.875
                   16      31        32    1.938
                 1000    1994      2000    1.994
              1000000 1999993   2000000    2.000
two-stack queue: ops = 6000, stack steps = 12000, worst single op = 1747, steps/op = 2.00

def counter_flips(n, bits=32):
    a = [0] * bits                    # a[0] = lowest bit
    flips = 0
    for _ in range(n):                # n times INCREMENT
        i = 0
        while i < bits and a[i] == 1:
            a[i] = 0                  # trailing 1s become 0
            flips += 1
            i += 1
        if i < bits:
            a[i] = 1                  # first 0 becomes 1
            flips += 1
    return flips
print("binary counter:   n   flips  2n-bound  flips/n")
for n in (8, 16, 1000, 1000000):
    f = counter_flips(n)
    print(f"{n:>21} {f:>7} {2 * n:>9} {f / n:>8.3f}")

inbox, outbox = [], []                # queue built from two stacks
ops = cost = worst = 0
def enqueue(x):
    global ops, cost, worst
    inbox.append(x); ops += 1; cost += 1; worst = max(worst, 1)
def dequeue():
    global ops, cost, worst
    c = 1
    if not outbox:                    # refill: move everything, reversing order
        while inbox:
            outbox.append(inbox.pop()); c += 2
    outbox.pop(); ops += 1; cost += c; worst = max(worst, c)

for i in range(1000):                 # pattern: 3 enqueues, then 2 dequeues
    for j in range(3):
        enqueue(3 * i + j)
    dequeue(); dequeue()
while inbox or outbox:
    dequeue()
print(f"two-stack queue: ops = {ops}, stack steps = {cost}, "
      f"worst single op = {worst}, steps/op = {cost / ops:.2f}")

binary counter:   n   flips  2n-bound  flips/n
                    8      15        16    1.875
                   16      31        32    1.938
                 1000    1994      2000    1.994
              1000000 1999993   2000000    2.000
two-stack queue: ops = 6000, stack steps = 12000, worst single op = 1747, steps/op = 2.00

আগে দেখা amortized যুক্তি — নতুন চোখে

• KMP (পর্ব ৫৮): matching-এর ভেতরের while লুপ দেখে O(nm) মনে হয়। Potential Φ = k (এখন পর্যন্ত মেলা দৈর্ঘ্য): প্রতিটি text-অক্ষরে k সর্বোচ্চ ১ বাড়ে, আর প্রতিটি prefix function-এর লাফ k-কে অন্তত ১ কমায়। k কখনো ঋণাত্মক নয়, তাই মোট লাফ ≤ মোট বৃদ্ধি ≤ n — KMP Θ(n + m). এটি হুবহু multipop-এর যুক্তি।
• Two pointer আর monotonic stack (পর্ব ১৬, ১৩): প্রতিটি pointer শুধু সামনে যায়, প্রতিটি উপাদান একবার ঢোকে আর একবার বের হয় — aggregate যুক্তি, মোট O(n).
• Hash table-এর rehashing (পর্ব ৩২): load factor সীমা ছাড়ালে bucket দ্বিগুণ — dynamic array-এর যুক্তিই।
• Union-find (পর্ব ৩৩): union by rank + path compression-এ m কাজে O(m α(n)) — α(n) বাস্তবে ৪-এর বেশি নয়। প্রমাণটি একটি সূক্ষ্ম potential function দিয়ে।

৮ · Amortized বনাম real-time নিশ্চয়তা

Amortized O(1) বলে “মোট দ্রুত” — প্রতিটি কাজ দ্রুত নয়। বেশিরভাগ প্রোগ্রামে মোটই আসল: একটি কনটেস্টের সমাধান বা রাতের ব্যাচ-কাজ শেষ পর্যন্ত কত সময় নিল, সেটাই মাপা হয়। কিন্তু কিছু সিস্টেমে প্রতিটি কাজের একটি সময়সীমা আছে, আর সেখানে একটি দামি কাজই বিপর্যয়।

• গেম আর অ্যানিমেশন: সেকেন্ডে ৬০ ফ্রেম মানে প্রতি ফ্রেমে প্রায় ১৬.৭ মিলিসেকেন্ড। একটি বিশাল vector-এর resize সেই সীমা ছাড়ালে স্ক্রিন একবার আটকে যায় — গড় যতই ভালো হোক।
• ওয়েব সার্ভার আর latency: লাখো অনুরোধের মধ্যে যে কয়টি দামি rehash-এর সময় পড়ল, তাদের উত্তর দেরিতে যায়। বড় সিস্টেম তাই গড়ের সাথে “সবচেয়ে ধীর ১%” (tail latency) মাপে।
• যন্ত্র নিয়ন্ত্রণ (real-time): গাড়ির ব্রেক বা পেসমেকারের সফটওয়্যারে “মোট ঠিক আছে” গ্রহণযোগ্য নয় — প্রতিটি কাজের worst case-ই সীমা।

সমাধান deamortization: দামি কাজটিকে ছোট টুকরো করে পরের কাজগুলোর মধ্যে ছড়িয়ে দেওয়া। Dynamic array-এ: c ঘরের ব্লক ভরলে 2c-এর নতুন ব্লক নিন, কিন্তু সাথে সাথে কপি করবেন না — পরের প্রতিটি push-এ নতুন উপাদান লেখার সাথে পুরোনো ব্লক থেকে ২টি করে সরান। c/2 push-এর মধ্যে সব c উপাদান সরে যায় — তখন নতুন ব্লকে 1.5c টি উপাদান, ভরার আগেই। প্রতিটি push এখন worst case O(1) (ধরে নিচ্ছি ব্লক বরাদ্দ ধ্রুবক সময়ে), দাম হলো জটিল কোড আর কিছুক্ষণ দুটি ব্লক রাখা। Redis তার hash table ঠিক এভাবে ধাপে ধাপে rehash করে; আর Robert Hood ও Robert Melville ১৯৮১ সালে দেখান, stack দিয়েই প্রতিটি কাজে worst case O(1)-এর queue বানানো যায়।

৯ · AI-এর যুগে amortized analysis — “O(1)” শব্দটির পেছনে কী লুকানো

AI সহকারীকে জিজ্ঞেস করলে প্রায় সবসময় শুনবেন “vector push_back O(1)” বা “এই লুপ O(n²), কারণ ভেতরে while আছে”. দুটোই অর্ধেক সত্য বা ভুল। Amortized যুক্তি কোডের চেহারা থেকে দেখা যায় না — দেখতে হয় কোন রাশি শুধু বাড়ে বা কমে। আর AI প্রায়ই “amortized” শব্দটি বাদ দেয়, average case-এর সাথে গুলিয়ে ফেলে, বা Φ বেছে নিয়ে Φ ≥ 0 পরীক্ষা করতে ভুলে যায়।

Amortized দাবি যাচাইয়ের চেকলিস্ট

• খরচের একক ঠিক করেছি (কপি, flip, stack-ধাপ), আর কোডে একটি counter বসিয়ে সেটিই গুনছি
• ছোট n-এ হাতে dry run করে মোট খরচ মিলিয়েছি, তারপর বড় n-এ মোট ÷ n স্থির থাকে কি না দেখেছি
• সবচেয়ে খারাপ ক্রম খুঁজেছি — সীমানায় push-pop, 0111…1-এ increment, বড় multipop — শুধু এলোমেলো ইনপুট নয়
• Potential-এ Φ(D₀) = 0 আর Φ ≥ 0 সত্যিই প্রমাণ করেছি; accounting-এ ব্যাংক কখনো ঋণাত্মক নয়
• এলোমেলো ক্রমে stress testing করে মোট খরচ ≤ দাবিকৃত সীমা assert করেছি, আর brute force সংস্করণের সাথে উত্তর মিলিয়েছি
• সমস্যাটি latency-সংবেদনশীল কি না ভেবেছি — তাহলে একক কাজের worst case আলাদা করে মেপেছি