Divide-and-conquer recurrence আর master theorem-এর গণিত

১ · ভেঙে সমাধান — T(n) = aT(n/b) + f(n)

এই মডিউলের আগের তিন পর্বে recurrence-এর সূচক এক বা দুই করে কমেছে: পর্ব ৪৪ “Recurrence দিয়ে মডেল — Fibonacci, Hanoi আর bit string”, পর্ব ৪৫ “Linear recurrence সমাধান — characteristic equation” আর পর্ব ৪৬ “Non-homogeneous recurrence আর particular solution”. সেখানে a_n নির্ভর করত a_n−1, a_n−2-এর ওপর। এই পর্বে আকার কমে ভাগ হয়ে: n থেকে সরাসরি n/2 বা n/3. এমন recurrence আসে divide and conquer algorithm থেকে, আর এদের সমাধানের পদ্ধতিও আলাদা।

দুটি পরিচিত উদাহরণ। Binary search সাজানো তালিকার মাঝের উপাদানটি দেখে, তারপর এক অর্ধেকে নামে: a = 1, b = 2, f(n) = 1, তাই T(n) = T(n/2) + 1. বাজারঘরের দশ লাখ invoice-এর সাজানো তালিকায় একটি নম্বর খুঁজতে বড়জোর ২০টি তুলনা লাগে। Merge sort তালিকাকে দুই অর্ধেক করে, দুটিকেই সাজায়, তারপর n-এর কাছাকাছি তুলনায় জোড়া দেয়: T(n) = 2T(n/2) + n. দুটির সঠিকতা আর floor-সহ নির্ভুল সমাধান strong induction দিয়ে পর্ব ১১ “Strong induction আর well-ordering”-এ প্রমাণিত; এখানে আমরা সাধারণ ছাঁচটির গণিত চাই।

একটি নিজে মডেল করার উদাহরণ। বাজারঘরের n-টি দিনের বিক্রির মধ্যে সবচেয়ে বড়টি খুঁজতে একজন প্রোগ্রামার “ভেঙে খোঁজা” লিখলেন: তালিকা দুই অর্ধেক করে প্রতিটি অর্ধেকের সর্বোচ্চ আলাদাভাবে বের করা, তারপর একটি তুলনায় দুটির বড়টি নেওয়া। তুলনার সংখ্যা M(1) = 0, M(n) = 2M(n/2) + 1. n = 2^k-এ খুলে লিখলে M = 1 + 2 + 4 + … + 2^k−1 = n − 1, ঠিক একটি সাধারণ loop-এর সমান। শিক্ষা: ভেঙে সমাধান করলেই কাজ কমে না; কমে শুধু যখন জোড়ার খরচ আর উপ-সমস্যার সংখ্যা মিলে লাভ দেয়। কখন দেয়, সেটিই এই পর্বের প্রশ্ন।

উত্তর সাধারণত নির্ভুল সূত্রে নয়, বৃদ্ধির হারে বলা হয়। তার জন্য তিনটি চিহ্ন লাগে। এদের algorithm-এর দিক DSA কোর্সের পর্ব ০৪-এ আছে; এখানে নিখুঁত সংজ্ঞা দিচ্ছি, কারণ প্রমাণে এগুলোই ব্যবহার হবে।

এই পর্বে lg n মানে log₂ n. Θ-এর ভেতরে logarithm-এর ভিত্তি গুরুত্বহীন, কারণ log_b n = lg n / lg b, অর্থাৎ শুধু একটি ধ্রুবক গুণক। কিন্তু সূচকে ভিত্তি খুব গুরুত্বপূর্ণ: n^{log₂ 3} ≈ n^1.585 আর n^{log₄ 3} ≈ n^0.792 একেবারে আলাদা হারে বাড়ে। পরীক্ষায় এই দুটি গুলিয়ে ফেলা খুব সাধারণ ভুল।

২ · Floor, ceiling আর n = b^k ধরে নেওয়ার সৎ যুক্তি

বাস্তবের merge sort বিজোড় n-এ দুই সমান অর্ধেক পায় না: এক ভাগে ⌈n/2⌉, অন্যটিতে ⌊n/2⌋. পর্ব ১১-এ দেখেছেন, সবচেয়ে খারাপ ক্ষেত্রে merge sort-এর তুলনার নির্ভুল সংখ্যা M(n) = n⌈lg n⌉ − 2^{⌈lg n⌉} + 1. এই সূত্র ঢেউয়ের মতো ওঠানামা করে, n = 2^k-এ এক রকম, মাঝখানে আরেক রকম। তবু বৃদ্ধির হার Θ(n lg n) সব n-এ একই। পাঠ্যবইগুলো তাই প্রায় সবসময় বলে, “ধরি n = 2^k”. প্রশ্ন হলো, এটি কেন বৈধ, আর কখন অবৈধ। উত্তরটি দুটি শর্তে।

1. যেকোনো বড় n-এর জন্য একটি k আছে যাতে b^k ≤ n < b^k+1. — ঘাতগুলো সব ধনাত্মক সংখ্যাকে ফাঁক ছাড়া ঢাকে
2. ঘাতগুলোতে ধ্রুবক c₁, c₂ আছে: c₁g(b^j) ≤ T(b^j) ≤ c₂g(b^j). আর মসৃণতা থেকে একটি ধ্রুবক s আছে: g(bm) ≤ s · g(m). — অনুমান
3. ওপরের সীমা: T(n) ≤ T(b^k+1) ≤ c₂g(b^k+1) ≤ c₂s · g(b^k) ≤ c₂s · g(n). — T আর g non-decreasing, মসৃণতা
4. নিচের সীমা: T(n) ≥ T(b^k) ≥ c₁g(b^k) ≥ (c₁/s) · g(b^k+1) ≥ (c₁/s) · g(n). — একই যুক্তি উল্টো দিকে
5. ধ্রুবক c₂s আর c₁/s n-এর ওপর নির্ভর করে না, তাই T(n) = Θ(g(n)). ∎ — সংজ্ঞা ১.২

দুটি শর্তই সত্যিই লাগে। মসৃণতা ছাড়া ধাপ ৩ ভাঙে: b^k আর b^k+1-এর মাঝে g অনেক গুণ বাড়তে পারে। Monotonicity ছাড়া ঘাতগুলো আমাদের ঠকাতে পারে: ধরুন T(n) = n যখন n দুইয়ের ঘাত, নইলে n². ঘাতগুলোতে দেখলে T = Θ(n) মনে হয়, অথচ সব n-এ তা মিথ্যা। তাই “ধরি n = 2^k” বলার পর T non-decreasing তা দেখানো সৎ প্রমাণের অংশ। Merge sort-এর ধাঁচে সেটা সহজ।

1. ভিত্তি n = 1: T(2) = 2T(1) + f(2) ≥ T(1), কারণ T(1) ≥ 0 আর f(2) ≥ 0. — সরাসরি
2. অনুমান: n ≥ 2, আর সব m < n-এ T(m) ≤ T(m + 1); ফলে 1 থেকে n পর্যন্ত T non-decreasing. — strong induction (পর্ব ১১)
3. ⌈n/2⌉ ≤ ⌈(n+1)/2⌉ আর ⌊n/2⌋ ≤ ⌊(n+1)/2⌋, আর n ≥ 2-এ দুটি নতুন আকারই ≤ n. — floor-ceiling-এর ধর্ম
4. তাই অনুমান থেকে T(⌈n/2⌉) ≤ T(⌈(n+1)/2⌉), T(⌊n/2⌋) ≤ T(⌊(n+1)/2⌋), আর f(n) ≤ f(n + 1). তিনটি যোগ করলে T(n) ≤ T(n + 1). ∎ — ধাপ ২, ৩

আরও সাধারণ ক্ষেত্রে, যেমন T(⌈n/b⌉), পাঠ্যবইগুলো আরেকটি পথ নেয়: ceiling-এর পর আকার n/b^j + b/(b − 1)-এর বেশি হয় না, আর এই ছোট বাড়তি অংশ Θ বদলায় না (CLRS-এর master theorem অধ্যায়ের floor-ceiling অংশ)। আমরা এখন থেকে n = b^k ধরে কাজ করব, আর উপপাদ্য ২.২ মনে রাখব।

৩ · Recursion tree — স্তর ধরে খরচের যোগ

T(n) = aT(n/b) + f(n) একটি গাছ আঁকে। মূলে আকার n-এর একটি সমস্যা, নিজস্ব খরচ f(n). তার a-টি সন্তান, প্রতিটি আকার n/b, প্রতিটির নিজস্ব খরচ f(n/b). এভাবে আকার 1-এ পৌঁছানো পর্যন্ত। এই গাছই recursion tree. মোট খরচ হলো সব node-এর নিজস্ব খরচের যোগ, আর সবচেয়ে সুবিধাজনক উপায় হলো স্তর ধরে যোগ করা। বারবার নিজের ভেতরে বসিয়ে খুলে লেখার এই পদ্ধতিকে iteration বা unrolling method-ও বলে।

1. ভিত্তি k = 0: n = 1, যোগফলটি ফাঁকা, দুই পাশেই T(1). — সরাসরি
2. অনুমান: k-এর জন্য সূত্রটি সত্য। — induction (পর্ব ১০)
3. ধাপ: m = b^k+1 হলে T(m) = aT(b^k) + f(m) = a^k+1T(1) + ∑_j=0^k−1 a^j+1 f(b^k−j) + f(m). সূচক i = j + 1 বসালে যোগফলটি ∑_i=1^k aⁱ f(m/bⁱ), আর বাড়তি f(m) হলো i = 0-এর পদ। ফলে সূত্রটি k + 1-এ সত্য। — recurrence, সূচক বদল
4. পাতার সংখ্যা: a^{log_b n} আর n^{log_b a}-এর log_b নিলে দুটিই (log_b n)(log_b a), আর log_b এক-এক ফাংশন, তাই সংখ্যা দুটি সমান। ∎ — logarithm-এর নিয়ম

ধাপ ৪-এর অভেদটি পরীক্ষায় খুব কাজের: T(n) = 9T(n/3) + … আর n = 81 হলে পাতা 9⁴ = 6561 = 81². ফাংশন n^{log_b a} পাতার মোট খরচ মাপে; DSA কোর্স একে watershed ফাংশন বলে। নিচের stepper সবচেয়ে চেনা গাছটি, T(n) = 2T(n/2) + n, n = 16-এ স্তর ধরে যোগ করে।

1স্তর ০: 1 × 16 = 162স্তর ১: 2 × 8 = 163স্তর ২: 4 × 4 = 164স্তর ৩: 8 × 2 = 165পাতা: 16 × T(1) = 166মোট 4 · 16 + 16 = 80

নিচের ব্লক যেকোনো a, b, f-এর জন্য এই স্তর-টেবিল ছাপে, আর স্তরের যোগকে recurrence সরাসরি চালানোর ফলের সঙ্গে মেলায়। প্রথমবার চালালে ব্রাউজারে Python (Pyodide) নামতে কয়েক সেকেন্ড লাগে।

def T(a, b, f, n):                    # direct recursion, n a power of b
    return 1 if n == 1 else a * T(a, b, f, n // b) + f(n)

def tree(a, b, f, n, name):           # recursion tree, one row per level
    print(name, " n =", n)
    total, j, size = 0, 0, n
    while size > 1:
        s = a ** j * f(size)          # a^j nodes, each costing f(n/b^j)
        print(f"  level {j}: {a ** j:4} nodes x f({size:2}) = {s:5}")
        total += s
        j, size = j + 1, size // b
    print(f"  leaves : {a ** j:4} x T(1)        = {a ** j:5}")
    total += a ** j
    print("  sum of levels =", total, "  direct T(n) =", T(a, b, f, n))

tree(2, 2, lambda m: m, 32, "T(n) = 2T(n/2) + n")
tree(3, 2, lambda m: m, 32, "T(n) = 3T(n/2) + n")
tree(2, 2, lambda m: m * m, 32, "T(n) = 2T(n/2) + n^2")

T(n) = 2T(n/2) + n  n = 32
  level 0:    1 nodes x f(32) =    32
  level 1:    2 nodes x f(16) =    32
  level 2:    4 nodes x f( 8) =    32
  level 3:    8 nodes x f( 4) =    32
  level 4:   16 nodes x f( 2) =    32
  leaves :   32 x T(1)        =    32
  sum of levels = 192   direct T(n) = 192
T(n) = 3T(n/2) + n  n = 32
  level 0:    1 nodes x f(32) =    32
  level 1:    3 nodes x f(16) =    48
  level 2:    9 nodes x f( 8) =    72
  level 3:   27 nodes x f( 4) =   108
  level 4:   81 nodes x f( 2) =   162
  leaves :  243 x T(1)        =   243
  sum of levels = 665   direct T(n) = 665
T(n) = 2T(n/2) + n^2  n = 32
  level 0:    1 nodes x f(32) =  1024
  level 1:    2 nodes x f(16) =   512
  level 2:    4 nodes x f( 8) =   256
  level 3:    8 nodes x f( 4) =   128
  level 4:   16 nodes x f( 2) =    64
  leaves :   32 x T(1)        =    32
  sum of levels = 2016   direct T(n) = 2016

৪ · Master theorem আর তার পূর্ণ প্রমাণ

f(n) = n^d হলে স্তর j-এর যোগ a^j(n/b^j)^d = n^d · (a/b^d)^j. অর্থাৎ স্তরগুলো একটি geometric series, যার অনুপাত q = a/b^d. Geometric series-এর যোগ পর্ব ১৭ “Sequence আর summation — closed form আর বিখ্যাত যোগফল”-এ প্রমাণিত: q ≠ 1 হলে ∑_j=0^k−1 q^j = (q^k − 1)/(q − 1). বাকিটা শুধু q-কে 1-এর সঙ্গে তুলনা। এই ফলটির নাম master theorem.

তিন case-এর শর্ত আসলে এক কথা: d < log_b a ⇔ b^d < a ⇔ q > 1. Case-এর নম্বর DSA কোর্স আর বেশিরভাগ বইয়ের মতো রাখা হলো: case 1-এ পাতা জেতে, case 3-এ মূল জেতে।

1. স্তর-যোগ: লেমা ৩.১ থেকে T(n) = c₀a^k + S, যেখানে S = ∑_j=0^k−1 a^jf(n/b^j). — লেমা ৩.১
2. চাপা দেওয়া: f-এর সীমা থেকে c₁n^dQ ≤ S ≤ c₂n^dQ, যেখানে Q = ∑_j=0^k−1 q^j, কারণ a^j(n/b^j)^d = n^dq^j. আর a^k = n^{log_b a}. — বীজগণিত, লেমা ৩.১-এর ধাপ ৪
3. Case 3 (q < 1): 1 ≤ Q ≤ 1/(1 − q), কারণ প্রথম পদ 1 আর অসীম যোগফল 1/(1 − q). তাই S = Θ(n^d). আর log_b a < d বলে পাতা c₀n^{log_b a} ≤ c₀n^d. যোগ করলে c₁n^d ≤ T(n) ≤ (c₂/(1 − q) + c₀)n^d. — geometric series
4. Case 2 (q = 1): Q = k = log_b n, আর a^k = n^d. তাই c₁n^d log_b n ≤ T(n) ≤ c₂n^d log_b n + c₀n^d, অর্থাৎ Θ(n^d log n). — k-টি সমান পদ
5. Case 1 (q > 1): Q = (q^k − 1)/(q − 1) < q^k/(q − 1), আর q^k = a^k/b^dk = n^{log_b a}/n^d. তাই S < c₂n^{log_b a}/(q − 1). নিচের দিকে T(n) ≥ c₀a^k = c₀n^{log_b a}. ফলে c₀n^{log_b a} ≤ T(n) ≤ (c₀ + c₂/(q − 1))n^{log_b a}. — geometric series, পাতার স্তর
6. তিন ক্ষেত্রেই ধ্রুবকগুলো n-এর ওপর নির্ভর করে না, তাই দাবি করা Θ-সীমা প্রমাণিত। ∎ — সংজ্ঞা ১.২

প্রমাণটি একটি ছবিতে ধরা যায়। Geometric series-এ q < 1 হলে প্রথম পদই প্রধান (মূল), q > 1 হলে শেষ পদ প্রধান (পাতা), আর q = 1 হলে সব পদ সমান, তাই পদের সংখ্যা log n গুণক হয়ে আসে। f(n) ঠিক n^d আর T(1) = 1 হলে নির্ভুল সূত্রও বেরিয়ে আসে: q ≠ 1-এ T(n) = n^{log_b a} + n^d(q^k − 1)/(q − 1). যেমন T(n) = 3T(n/2) + n-এ q = 3/2, আর হিসাব করলে T(n) = 3n^{lg 3} − 2n. নিচের ব্লক চারটি recurrence-এর নির্ভুল মান বের করে, বন্ধ সূত্রের সঙ্গে assert দিয়ে মেলায়, তারপর Θ-অনুমানের সঙ্গে অনুপাত দেখায়।

from fractions import Fraction

def T(a, f, k):                       # exact T(2^k) with T(1) = 1, b = 2
    t = 1
    for i in range(1, k + 1):         # bottom-up: T(2^i) = a*T(2^(i-1)) + f
        t = a * t + f(2 ** i, i)
    return t

cases = [  # recurrence, Theta guess, a, f(n, lg n), g(n, lg n), closed form
    ("T(n/2)+1", "lg n", 1, lambda n, k: 1, lambda n, k: k,
     lambda n, k: k + 1),
    ("2T(n/2)+n", "n lg n", 2, lambda n, k: n, lambda n, k: n * k,
     lambda n, k: n * k + n),
    ("3T(n/2)+n", "n^lg3", 3, lambda n, k: n, lambda n, k: 3 ** k,
     lambda n, k: 3 ** (k + 1) - 2 * n),
    ("2T(n/2)+n^2", "n^2", 2, lambda n, k: n * n, lambda n, k: n * n,
     lambda n, k: 2 * n * n - n),
]
print("T(n)/g(n) at n = 2^4, 2^8, 2^16, 2^24")
for name, label, a, f, g, exact in cases:
    ratios = []
    for k in (4, 8, 16, 24):
        n, t = 2 ** k, T(a, f, k)
        assert t == exact(n, k)       # closed form checked exactly
        ratios.append(f"{float(Fraction(t, g(n, k))):.4f}")
    print(f"{name:12} g = {label:7}", "  ".join(ratios))

T(n)/g(n) at n = 2^4, 2^8, 2^16, 2^24
T(n/2)+1     g = lg n    1.2500  1.1250  1.0625  1.0417
2T(n/2)+n    g = n lg n  1.2500  1.1250  1.0625  1.0417
3T(n/2)+n    g = n^lg3   2.6049  2.9220  2.9970  2.9999
2T(n/2)+n^2  g = n^2     1.9375  1.9961  2.0000  2.0000

Algorithm নকশায় এর অর্থ। তিন case তিন রকম পরামর্শ দেয়। Case 1-এ (পাতা-ভারী) উত্তর n^{log_b a}, যেখানে f একেবারেই নেই: জোড়ার খরচ কমিয়ে লাভ নেই, লাভ শুধু উপ-সমস্যার সংখ্যা a কমালে, যা Karatsuba আর Strassen করেছেন। Case 3-এ (মূল-ভারী) উত্তর f(n): এখানে উল্টো, recursion প্রায় বিনা খরচের, তাই মূলের ভাঙা-জোড়ার কাজ দ্রুত করাই একমাত্র পথ। Case 2-এ (সুষম) দুই দিকই সমান ভারী, আর বাড়তি log n গুণকটি আসে স্তরের সংখ্যা থেকে; merge sort এই ভারসাম্যের সবচেয়ে চেনা উদাহরণ। তাই কোনো নতুন পদ্ধতির খরচ কমাতে চাইলে আগে দেখুন গাছটি কোন দিকে ভারী।

৫ · Case বাছাই ধাপে ধাপে, আর পরিচিত algorithm-এর হিসাব

পরীক্ষায় master theorem প্রয়োগ একটি নির্দিষ্ট ক্রমে করলে ভুল কম হয়: a, b, d পড়া; log_b a বের করা; d-এর সঙ্গে তুলনা (বা q = a/b^d-কে 1-এর সঙ্গে); case থেকে উত্তর। নিচের stepper এই ক্রম T(n) = 3T(n/2) + n-এ দেখায়।

1a = 3, b = 2, f(n) = n2log₂ 3 ≈ 1.5853d = 1 < 1.585 ⇒ case 14স্তর: 16, 24, 36, 54, 815T(n) = Θ(n^1.585)6n = 1024: অনুপাত ≈ 2.97

একই তিন ধাপে পরিচিত algorithm-গুলোর হিসাব। এদের code আর বিস্তারিত বিশ্লেষণ DSA কোর্সের পর্ব ০৯ আর পর্ব ৪৯-এ; এখানে শুধু গণিত।

টেবিলের একটি শিক্ষা: সরল ভাগে matrix গুণ 8T(n/2) + n² = Θ(n³), সাধারণ পদ্ধতির চেয়ে একটুও ভালো নয়। Divide and conquer নিজে কিছু বাঁচায় না; বাঁচায় a কমানো। Case 1-এ উত্তর শুধু a আর b-এর ওপর নির্ভর করে, f-এর ওপর নয়, তাই উপ-সমস্যা একটি কমালেই সূচক কমে। Karatsuba আর Strassen-এর পুরো কৌশল এটিই।

৬ · Karatsuba আর Strassen — একটি গুণ কম, সূচক কম

দুটি n-অঙ্কের সংখ্যা স্কুলের নিয়মে গুণ করলে প্রতিটি অঙ্ককে প্রতিটি অঙ্কের সঙ্গে গুণ করতে হয়: n²টি এক-অঙ্কের গুণ। একে schoolbook multiplication বলে। ধরুন n জোড়, m = n/2, আর x = a · 10^m + b, y = c · 10^m + d, যেখানে a, b, c, d প্রতিটি m-অঙ্কের। তখন

xy = ac · 10^2m + (ad + bc) · 10^m + bd

সরলভাবে এখানে চারটি অর্ধেক-আকারের গুণ (ac, ad, bc, bd), তাই T(n) = 4T(n/2) + Θ(n) = Θ(n²): কোনো লাভ নেই। Karatsuba-র পর্যবেক্ষণ হলো মাঝের পদটি আলাদা দুটি গুণ ছাড়াই পাওয়া যায়।

1. (a + b)(c + d) = ac + ad + bc + bd. — বণ্টন নিয়ম
2. দুই পাশ থেকে ac + bd বিয়োগ করলে (a + b)(c + d) − ac − bd = ad + bc. ∎ — বীজগণিত

উদাহরণ 1234 × 5678: a = 12, b = 34, c = 56, d = 78. ac = 672, bd = 2652, (12 + 34)(56 + 78) = 46 × 134 = 6164, তাই মাঝের পদ 6164 − 672 − 2652 = 2840. ফল 672 · 10⁴ + 2840 · 10² + 2652 = 7006652, যা 1234 × 5678-এর সঙ্গে মেলে। যোগ-বিয়োগ আর 10-এর ঘাতে সরানো Θ(n) খরচের, তাই T(n) = 3T(n/2) + Θ(n), যা §৫-এর stepper অনুযায়ী Θ(n^{lg 3}). নিচের ব্লক ছোট (প্রায় এক-অঙ্কের) গুণ গুনে দেখে, সময় মাপে না।

import random

count = {"mul": 0, "big": 0}

def karatsuba(x, y, n):               # x, y below 10^n, n a power of 2
    if n == 1:
        count["mul"] += 1             # one small multiplication
        count["big"] = max(count["big"], x, y)
        return x * y
    m = n // 2
    a, b = divmod(x, 10 ** m)         # x = a*10^m + b
    c, d = divmod(y, 10 ** m)
    ac = karatsuba(a, c, m)
    bd = karatsuba(b, d, m)
    s = karatsuba(a + b, c + d, m) - ac - bd     # = ad + bc
    return ac * 10 ** (2 * m) + s * 10 ** m + bd

random.seed(47)
print(" digits  Karatsuba  schoolbook  ratio   3^k = n^lg3")
for k in range(9):
    n = 2 ** k
    x = random.randrange(10 ** (n - 1), 10 ** n)
    y = random.randrange(10 ** (n - 1), 10 ** n)
    count["mul"] = 0
    assert karatsuba(x, y, n) == x * y
    print(f"{n:6} {count['mul']:10} {n * n:11} {count['mul'] / n**2:6.3f}"
          f" {3 ** k:9}")
print("largest operand in a small multiplication:", count["big"])

 digits  Karatsuba  schoolbook  ratio   3^k = n^lg3
     1          1           1  1.000         1
     2          3           4  0.750         3
     4          9          16  0.562         9
     8         27          64  0.422        27
    16         81         256  0.316        81
    32        243        1024  0.237       243
    64        729        4096  0.178       729
   128       2187       16384  0.133      2187
   256       6561       65536  0.100      6561
largest operand in a small multiplication: 56

Strassen-এর matrix গুণ একই ভাবনা। দুটি n × n matrix-কে চারটি করে n/2 × n/2 খণ্ডে ভাগ করলে সরল পদ্ধতিতে খণ্ডের ৮টি গুণ লাগে। Strassen ১৯৬৯ সালে এমন ৭টি গুণফল দেখান, যাদের যোগ-বিয়োগে (প্রায় ১৮টি খণ্ড-যোগ) চারটি ফল-খণ্ডই পাওয়া যায়। ফলে T(n) = 7T(n/2) + Θ(n²), log₂ 7 ≈ 2.807 > 2, case 1: Θ(n^2.807). n = 2¹⁰ = 1024 হলে পাতার স্তরে 7¹⁰ = 282,475,249টি সংখ্যা-গুণ, সরল ভাগে 8¹⁰ = 1,073,741,824টি: প্রায় ২৬%. Boolean matrix আর matrix-এর discrete ব্যবহার পর্ব ১৯ “Discrete math-এ matrix — 0-1 matrix আর Boolean product”-এ আছে।

Closest pair কেন n log n. সমতলের n-টি বিন্দু (ধরুন বাজারঘরের ডেলিভারি পয়েন্ট) x-স্থানাঙ্কে সাজিয়ে একটি উল্লম্ব রেখায় দুই অর্ধেক করা হয়, প্রতিটি অর্ধেকে সবচেয়ে কাছের জোড়ার দূরত্ব δ_L, δ_R recursion দিয়ে আসে। δ = min(δ_L, δ_R). বাকি থাকে রেখার দুই পাশের জোড়া, আর সেগুলোর শুধু রেখার δ দূরত্বের ফালিতে থাকা বিন্দু দেখলেই চলে। একটি জ্যামিতিক pigeonhole যুক্তি দেখায়, ফালিতে y-অনুযায়ী সাজানো ক্রমে প্রতিটি বিন্দুকে শুধু পরের কয়েকটি (একটি ছোট ধ্রুবক সংখ্যক) বিন্দুর সঙ্গে মেলাতে হয়। তাই জোড়ার খরচ Θ(n), আর T(n) = 2T(n/2) + Θ(n) = Θ(n log n), যদি y-ক্রম আগে থেকে রাখা যায়। প্রতি ধাপে নতুন করে সাজালে খরচ Θ(n log n) হয়ে যায়, যার ফল §৭-এ দেখব। ধ্রুবকটির সঠিক মান আর code DSA কোর্সের পর্ব ৪৯-এ।

৭ · ছাঁচের বাইরে — n log n চালিকা, ফাঁক, regularity আর Akra–Bazzi

উপপাদ্য ৪.১ শুধু f(n) = Θ(n^d)-এর জন্য। বাস্তবে অন্য রূপও আসে। ধরুন closest pair algorithm প্রতিটি ধাপে বিন্দুগুলো নতুন করে সাজায়: তখন জোড়ার খরচ Θ(n log n), আর T(n) = 2T(n/2) + n lg n. এখানে d = 1 = log₂ 2, কিন্তু f ঠিক n¹ নয়। Recursion tree সরাসরি কাজ করে।

লক্ষ করুন, এই ফল case 2-এর মতো (n lg n) নয়, এক lg গুণক বেশি। সাধারণভাবে, d = log_b a আর f(n) = Θ(n^d lg^p n) হলে, p ≥ 0-এ T(n) = Θ(n^d lg^p+1 n). অনেক বই case 2-কে এই বর্ধিত রূপে লেখে। এর প্রমাণ উপরের মতোই: স্তরের যোগ n^d(k − j)^p-এর গুণিতক, আর ∑(k − j)^p = Θ(k^p+1).

দুই case-এর মাঝের ফাঁক। T(n) = 2T(n/2) + n/lg n নিন। n/lg n কি n-এর চেয়ে ছোট? হ্যাঁ। তাহলে কি case 1, উত্তর Θ(n)? না। Case 1-এর আসল শর্ত হলো f(n) = O(n^{log_b a − ε}) কোনো ধ্রুবক ε > 0-এর জন্য, অর্থাৎ f-কে polynomially ছোট হতে হবে। n/lg n যেকোনো n^1−ε-এর চেয়ে বড়, তাই কোনো case খাটে না। Recursion tree আবার উত্তর দেয়: স্তর j-এর যোগ 2^j · (n/2^j)/(k − j) = n/(k − j), তাই অ-পাতা স্তরের মোট n(1/k + … + 1/1) = n · H_k, যেখানে H_k একটি harmonic number (পর্ব ৪০). H_k ≈ ln k, তাই T(n) = Θ(n log log n): n-এর চেয়ে সামান্য বেশি, n log n-এর চেয়ে অনেক কম।

তৃতীয় case-এর শেষ শর্তটির নাম regularity condition: প্রতিটি নিচের স্তরের মোট খরচ ওপরেরটির একটি নির্দিষ্ট ভগ্নাংশের বেশি নয়, অর্থাৎ স্তরগুলো অন্তত geometric হারে কমে। f(n) = n^d হলে a(n/b)^d = q · n^d, তাই শর্তটি ঠিক q < 1, যা উপপাদ্য ৪.১-এ আপনিই মেটে। অদ্ভুত, দোলায়মান f-এ শর্তটি ভাঙতে পারে, তাই বক্তব্যে এটি রাখতে হয়। প্রমাণ উপপাদ্য ৪.১-এর মতোই স্তর-যোগে, শুধু অসমতাগুলো একটু জটিল; এখানে বাদ রাখছি।

চলক বদল। কিছু recurrence প্রথমে ছাঁচে পড়ে না, কিন্তু চলক বদলালে পড়ে। T(n) = 2T(√n) + lg n নিন, যা কিছু গাছ-ভিত্তিক তথ্য-কাঠামোয় আসে। m = lg n আর S(m) = T(2^m) বসালে √n = 2^m/2, তাই S(m) = 2S(m/2) + m: চেনা merge sort-এর ছাঁচ, S(m) = Θ(m lg m). ফিরে গেলে T(n) = Θ(lg n · lg lg n). T(2) = 1 নিলে n = 2¹⁶-এ নির্ভুল মান S(16) = 16 · 4 + 16 = 80, যা recurrence সরাসরি চালিয়ে scratch-এ মেলানো। চলক বদলের algorithm-এর দিক DSA কোর্সের পর্ব ০৮-এ আছে।

অসমান ভাগ। T(n) = T(n/3) + T(2n/3) + n-এ দুটি উপ-সমস্যা দুই আকারের, তাই a আর b নেই। Median of medians-এর T(n) = T(n/5) + T(7n/10) + n-ও এমন। এদের জন্য Mohamad Akra আর Louay Bazzi ১৯৯৮ সালে প্রকাশিত একটি সাধারণ ফল ব্যবহার হয়, যার একটি পরিমার্জিত রূপ Tom Leighton-এর নোটে আছে বলে জানা যায়।

প্রয়োগ। (১) T(n/3) + T(2n/3) + n: p = 1-এ 1/3 + 2/3 = 1, আর ∫ u/u² du = ln x, তাই Θ(n log n). (২) T(n/5) + T(7n/10) + n: p = 1-এ যোগ 0.9 < 1, তাই p < 1 (হিসাবে p ≈ 0.84); ∫ u^−p du ≈ x^1−p/(1 − p), গুণ করলে Θ(n). Master theorem এর বিশেষ ক্ষেত্র: m = 1, a₁ = a, b₁ = 1/b হলে a · b^−p = 1 থেকে p = log_b a. নিচের ব্লক floor-সহ তিনটি recurrence নির্ভুল পূর্ণসংখ্যায় চালিয়ে অনুপাত দেখায়।

from functools import lru_cache
from math import log2

@lru_cache(maxsize=None)
def split(n):                         # T(n) = T(n//3) + T(2n//3) + n
    return 1 if n < 3 else split(n // 3) + split(2 * n // 3) + n

@lru_cache(maxsize=None)
def mom(n):                           # T(n) = T(n//5) + T(7n//10) + n
    return 1 if n < 5 else mom(n // 5) + mom(7 * n // 10) + n

@lru_cache(maxsize=None)
def nlogn(n):                         # T(n) = 2T(n/2) + n lg n, n = 2^k
    return 1 if n == 1 else 2 * nlogn(n // 2) + n * (n.bit_length() - 1)

H = -(1/3) * log2(1/3) - (2/3) * log2(2/3)    # entropy of the split
print("n          split/(n lg n)   mom/n   nlogn/(n lg^2 n)")
for k in (10, 16, 22, 30, 40):
    n = 2 ** k
    print(f"2^{k:<7}  {split(n) / (n * k):14.4f}  {mom(n) / n:6.3f}"
          f"   {nlogn(n) / (n * k * k):10.4f}")
print(f"limits: 1/H = {1 / H:.4f},  10,  1/2")

n          split/(n lg n)   mom/n   nlogn/(n lg^2 n)
2^10               0.9688   6.019       0.5600
2^16               1.0157   7.944       0.5352
2^22               1.0359   8.941       0.5248
2^30               1.0530   9.565       0.5178
2^40               1.0614   9.856       0.5131
limits: 1/H = 1.0890,  10,  1/2

৮ · Substitution method — ব্যর্থ অনুমান, শক্ত অনুমান আর পরীক্ষার অঙ্ক

Recursion tree উত্তর খুঁজে দেয়; সবচেয়ে কড়া প্রমাণ প্রায়ই আসে substitution method থেকে: একটি সীমা অনুমান করে induction দিয়ে প্রমাণ। এর একটি বিখ্যাত ফাঁদ আছে। অনুমান সঠিক Θ হলেও induction আটকে যেতে পারে, আর তখন সমাধান হলো অনুমানকে শক্ত করা: একটি ছোট মাত্রার পদ বিয়োগ করা। শুনতে উল্টো লাগে, কিন্তু শক্ত দাবি মানে induction-এ শক্ত অনুমানও পাওয়া যায়।

1অনুমান: T(n) ≤ c·n²24c(n/2)² + n = cn² + n3cn² + n ≤ cn²? কখনো না4নতুন: T(n) ≤ cn² − n54(cn²/4 − n/2) + n = cn² − n ✓6ভিত্তি: 1 ≤ c − 1 ⇒ c = 2

যুক্তির ভুল ধরুন: “2T(n/2) + n = O(n)”

একজন লিখলেন: “দাবি: T(n) = 2T(n/2) + n, T(1) = 1 হলে T(n) = O(n). প্রমাণ: অনুমান T(m) ≤ cm. তাহলে T(n) ≤ 2c(n/2) + n = cn + n = (c + 1)n = O(n). ∎”

ভুল কোথায়: Induction-এ প্রমাণ করতে হয় একই c দিয়ে T(n) ≤ cn. পাওয়া গেল (c + 1)n: প্রতিটি স্তরে ধ্রুবক 1 করে বাড়ছে, আর lg n স্তরে তা c + lg n, যা ধ্রুবক নয়। আসল উত্তর T(n) = n lg n + n (§৩-এর stepper), যা O(n) নয়। এখানে শক্ত অনুমানেও লাভ নেই, কারণ দাবিটিই মিথ্যা। Substitution-এ “= O(…)” লিখে থামবেন না; সবসময় হুবহু অনুমানের রূপটি ফেরত আনুন।

অঙ্ক ১: নির্ভুল সূত্র আর Θ

T(1) = 1, T(n) = 8T(n/2) + n², n = 2^k. T(n)-এর বন্ধ সূত্র আর Θ বের করুন।

1. q = 8/2² = 2 > 1, case 1: Θ(n^{log₂ 8}) = Θ(n³).
2. নির্ভুল: T(n) = n³ + n²(2^k − 1)/(2 − 1) = n³ + n³ − n² = 2n³ − n².
3. যাচাই: T(2) = 8 + 4 = 12 = 16 − 4, T(16) = 7936 = 2 · 4096 − 256 (scratch-এ k ≤ 5 পর্যন্ত মেলানো)।

অঙ্ক ২: case 2 আর case 3 একসঙ্গে

(ক) T(n) = 4T(n/2) + n²; (খ) T(n) = T(n/2) + n; দুটিতেই T(1) = 1, n = 2^k.

1. (ক) q = 4/4 = 1, case 2: Θ(n² lg n). প্রতিটি স্তরে n², k স্তর আর পাতায় n²: T(n) = n²(lg n + 1); T(16) = 256 · 5 = 1280.
2. (খ) q = 1/2, case 3: Θ(n). নির্ভুল: 1 + (n + n/2 + … + 2) = 2n − 1; T(32) = 63.

অঙ্ক ৩: ভিত্তি 3 আর 4

(ক) T(n) = 9T(n/3) + n; (খ) T(n) = 2T(n/4) + √n.

1. (ক) log₃ 9 = 2 > 1, case 1: Θ(n²). T(1) = 1 হলে নির্ভুল (3n² − n)/2; T(27) = 1080.
2. (খ) log₄ 2 = 1/2 = d, case 2: Θ(√n log n). T(1) = 1 হলে নির্ভুল √n(log₄ n + 1); T(256) = 16 · 5 = 80.

অঙ্ক ৪: দুই algorithm-এর তুলনা

বাজারঘরের গুদাম-দূরত্বের matrix গুণের জন্য একজন একটি নতুন পদ্ধতি প্রস্তাব করলেন: T'(n) = a · T'(n/4) + n². সবচেয়ে বড় কোন পূর্ণসংখ্যা a-তে এটি Strassen-এর Θ(n^{log₂ 7})-এর চেয়ে asymptotically দ্রুত হবে?

1. a > 16 হলে log₄ a > 2, case 1: T'(n) = Θ(n^{log₄ a}). (a ≤ 16 হলে উত্তর Θ(n²) বা Θ(n² log n), যা এমনিতেই দ্রুত।)
2. দ্রুত হওয়ার শর্ত log₄ a < log₂ 7. কিন্তু log₄ a = (lg a)/2, তাই শর্তটি lg a < 2 lg 7 = lg 49, অর্থাৎ a < 49.
3. উত্তর a = 48. a = 49-এ log₄ 49 = log₂ 7 হুবহু, তাই সমান হারে বাড়ে, দ্রুত নয়। এখানে ভিত্তি বদলের নিয়মটিই অঙ্কের চাবি।

৯ · AI-এর যুগে — master theorem-এর উত্তর যাচাই

“T(n) = …-এর সমাধান চাই” লিখলে AI সহকারী সাধারণত এক লাইনে উত্তর দেয়, আর বেশিরভাগ সময় ঠিক। ভুলগুলো লুকিয়ে থাকে ঠিক সেই জায়গায়, যেখানে এই পর্বের সূক্ষ্মতা: সূচকে log-এর ভিত্তি, polynomially ছোট-বড়, regularity, অসমান ভাগ। এই বিষয়ে কয়েকটি ভুল নিয়মিত দেখা যায়:

AI-এর উত্তর হাতে পেলে — যাচাইয়ের চেকলিস্ট

• সূচকে log-এর ভিত্তি b কি না, আর পাতার সংখ্যা a^{log_b n} হাতে মিলিয়েছি
• চালিকা-খরচ সত্যিই Θ(n^d) কি না, নাকি log গুণক আছে, তা দেখেছি
• ভাগগুলো সমান কি না, আর recurrence সত্যিই n/b ধরনের (n − 1 নয়) তা দেখেছি
• Substitution-এর প্রতিটি ধাপে একই ধ্রুবক ফেরত এসেছে কি না যাচাই করেছি
• T(2^k) নির্ভুল পূর্ণসংখ্যায় চালিয়ে অনুপাত একটি ধ্রুবকে স্থির হচ্ছে কি না দেখেছি
• উদ্ধৃত সাল, নাম আর সূচকের মান বিশ্বস্ত উৎসে মিলিয়েছি

এই পর্বের প্রায় সব উত্তর একটি প্রশ্নে নেমে আসে: recursion tree-র স্তরগুলো বাড়ে, সমান থাকে, না কমে? AI-এর উত্তর পড়ার সময় নিজে প্রথম তিন স্তরের যোগ লিখে দেখুন। অনুপাত q চোখে পড়লেই case-টি নিজে বলতে পারবেন, আর ভুল উত্তর সাধারণত সেখানেই ধরা পড়ে।