লিখিত ও মৌখিক (ভাইভা) প্রশ্ন — প্রমাণসহ

সংজ্ঞা: অ্যালগরিদম হলো সুনির্দিষ্ট ধাপের একটি সসীম ক্রম, যা একটি সমস্যার প্রতিটি বৈধ ইনপুট (instance) থেকে সঠিক আউটপুট দেয়।

বৈশিষ্ট্য: (১) ইনপুট — শূন্য বা বেশি; (২) আউটপুট — অন্তত একটি; (৩) definiteness — প্রতিটি ধাপ দ্ব্যর্থহীন; (৪) finiteness — সসীম ধাপে থামে; (৫) effectiveness — প্রতিটি ধাপ কাগজ-কলমে করা যায় এমন সরল। সাথে বলুন: সঠিকতা (সব ইনপুটে) আর দক্ষতা (সময় ও জায়গা)।

RAM model: Random Access Machine একটি কল্পিত কম্পিউটার — যোগ, গুণ, তুলনা, মেমরির যেকোনো ঘর পড়া বা লেখা প্রতিটি এক ধাপ (ধ্রুবক সময়), আর নির্দেশ চলে একটির পর একটি। কেন লাগে: আসল মেশিন, compiler আর ভাষা বদলালে সেকেন্ডের হিসাব বদলায়; ধাপ গুনলে অ্যালগরিদমের তুলনা যন্ত্র-নিরপেক্ষ হয়।

নম্বর কোথায়: পাঁচটি বৈশিষ্ট্যের নাম ও এক লাইনের অর্থ, আর RAM model-এ “প্রতিটি মৌলিক কাজ এক ধাপ” কথাটি। পর্ব ০২

Pseudocode: INSERTION-SORT(a[0..n-1])      // 0-based
for i = 1 to n-1:
    key = a[i]
    j = i
    while j > 0 and a[j-1] > key:
        a[j] = a[j-1]          // shift bigger item right
        j = j - 1
    a[j] = key

Invariant: বাইরের লুপের প্রতিটি ঘোরার শুরুতে a[0..i-1] অংশে আছে মূল অ্যারের প্রথম iটি উপাদানই, এবং সেগুলো সাজানো।

• শুরু: i = 1-এ অংশটি শুধু a[0] — একটি উপাদান নিজেই সাজানো। সত্য।
• রক্ষা: ভেতরের লুপ key-এর চেয়ে বড় উপাদানগুলোকে এক ঘর ডানে সরায়, ক্রম না ভেঙে। থামে যখন j = 0 অথবা a[j-1] ≤ key. তখন a[0..j-1]-এর সবাই ≤ key আর a[j+1..i]-এর সবাই > key, তাই a[j] = key বসালে a[0..i] সাজানো, আর এতে আছে প্রথম i+1টি উপাদানই। পরের ঘোরার জন্য invariant সত্য।
• সমাপ্তি: লুপ থামে i = n-এ। invariant বলছে a[0..n-1] — পুরো অ্যারে — মূল উপাদানগুলো নিয়েই সাজানো। ∎

উদাহরণ: [5, 2, 4, 6, 1, 3] → i=1: [2, 5, 4, 6, 1, 3] → i=2: [2, 4, 5, 6, 1, 3] → i=3: অপরিবর্তিত → i=4: [1, 2, 4, 5, 6, 3] → i=5: [1, 2, 3, 4, 5, 6].

Complexity: উল্টো সাজানো ইনপুটে i-তম ঘোরায় i টি তুলনা, মোট 1 + 2 + … + (n−1) = n(n−1)/2 = Θ(n²). সাজানো ইনপুটে প্রতি ঘোরায় ১টি, মোট n − 1 = Θ(n). জায়গা Θ(1) বাড়তি (in-place). গ-০৫-এর পরের প্রোগ্রামটি সব ইনপুট চালিয়ে n = 8-এ worst case 28 = 8·7/2 পেয়েছে।

নম্বর কোথায়: invariant-এর নির্ভুল বাক্য (“প্রথম i টি উপাদানই, সাজানো” — দুই অংশই), তিনটি ধাপের নাম, আর সমাপ্তিতে থামার শর্ত (i = n) ব্যবহার। পর্ব ০৩ · পর্ব ২০

সংজ্ঞা: f(n) = O(g(n)) যদি এমন ধনাত্মক ধ্রুবক c আর n0 থাকে যে সব n ≥ n0-এর জন্য 0 ≤ f(n) ≤ c·g(n). অর্থাৎ একটা সময়ের পর f কখনো g-এর একটি ধ্রুবক গুণের ওপরে ওঠে না — upper bound.

প্রমাণ ১: n ≥ 1 হলে 5n ≤ 5n² আর 2 ≤ 2n². তাই 3n² + 5n + 2 ≤ 3n² + 5n² + 2n² = 10n². সুতরাং c = 10, n0 = 1 নিলে সংজ্ঞা পূরণ হয়। ∎ (অন্য জোড়াও চলে: c = 4 নিলে দরকার 5n + 2 ≤ n², যা n = 6-এ 32 ≤ 36 আর তার পরে সবসময় সত্য, কিন্তু n = 5-এ 27 > 25 — তাই n0 = 6. c আর n₀ একক নয়, একটি জোড়া দেখালেই যথেষ্ট।)

প্রমাণ ২ (contradiction): ধরুন n² = O(n). তাহলে কোনো c, n₀-এর জন্য সব n ≥ n₀-এ n² ≤ cn, অর্থাৎ n ≤ c. কিন্তু n = max(n₀, ⌊c⌋ + 1) নিলে n > c — বিরোধ। তাই n² ≠ O(n). ∎

নম্বর কোথায়: সংজ্ঞায় “কোনো c > 0 আর n₀ আছে, সব n ≥ n₀-এর জন্য” — তিনটি অংশই; প্রমাণে c আর n₀-এর নির্দিষ্ট মান, আর অসমতার প্রতিটি ধাপ কোন n-এর জন্য সত্য তা লেখা। পর্ব ০৪

প্রমাণ: দরকার c₁n² ≤ (1/2)n² − 3n ≤ c₂n². n² দিয়ে ভাগ করে: c₁ ≤ 1/2 − 3/n ≤ c₂. ডান দিক n ≥ 1-এ সবসময় সত্য, যদি c₂ = 1/2. বাঁ দিকে 1/2 − 3/n বাড়তে থাকে; n = 7-এ মান 1/2 − 3/7 = 1/14 > 0. তাই c1 = 1/14, c2 = 1/2, n0 = 7. (n = 6-এ মান 0, তাই সেখান থেকে শুরু করা যায় না।) ∎

যোগ করুন: Θ মানে “O এবং Ω দুটোই”. Big-O মানেই worst case নয় — যেকোনো ফাংশনের সীমা; “insertion sort-এর best case Θ(n)” একটি সঠিক বাক্য।

নম্বর কোথায়: তিন সংজ্ঞায় অসমতার দিক ঠিক; প্রমাণে তিনটি ধ্রুবকের নির্দিষ্ট মান আর n₀ কেন ৭ (৬ নয়) — এই ছোট যাচাই। পর্ব ০৪

Recursion tree: মূলে কাজ n. তলা ১-এ দুটি node, প্রতিটি n/2 — মোট n. তলা i-তে 2ⁱটি node, প্রতিটি n/2ⁱ — মোট n. আকার 1 হয় যখন n/2ⁱ = 1, অর্থাৎ i = log n. ভেতরের তলা log n টি (i = 0 থেকে log n − 1), প্রতিটিতে n; পাতার তলায় n টি পাতা, প্রতিটি T(1) = 1, মোট n. তাই

নিচের ডায়াগ্রামে n = 8 ধরে গাছটি ধাপে ধাপে আঁকা হয়েছে: 8 + 8 + 8 + 8 = 32 = 8·3 + 8.

Substitution (অনুমান ও induction): দাবি — সব n ≥ 2 (2-এর ঘাত)-এর জন্য T(n) ≤ c·n log n, যেখানে c = 2.

• Base: n = 2: T(2) = 2·1 + 2 = 4, আর c·2·log 2 = 2·2·1 = 4. 4 ≤ 4 ✓. (n = 1 base হিসেবে নেওয়া যায় না, কারণ 1·log 1 = 0 < T(1) — এটাই এই প্রমাণের সাধারণ ফাঁদ।)
• Hypothesis: ধরুন T(n/2) ≤ c·(n/2)·log(n/2), যেখানে n/2 ≥ 2.
• Step: T(n) = 2T(n/2) + n ≤ 2c(n/2)(log n − 1) + n = c·n log n − cn + n ≤ c·n log n, কারণ c ≥ 1 হলে −cn + n ≤ 0. ∎

নিচের Ω দিকটিও একইভাবে: T(n) ≥ n log n (base n = 2: 4 ≥ 2), তাই T(n) = Θ(n log n). এই recurrence-ই merge sort-এর।

নম্বর কোথায়: প্রতি তলার খরচ আর তলার সংখ্যা (log n + 1) আলাদা করে লেখা, পাতার খরচ ভুলে না যাওয়া; substitution-এ base case বেছে নেওয়ার যুক্তি, আর step-এ ঠিক কোথায় c ≥ 1 লাগল। পর্ব ০৮

বিবৃতি: a ≥ 1, b > 1 ধ্রুবক, আর T(n) = aT(n/b) + f(n). f(n)-কে মেলান watershed ফাংশন n^{log_b a}-এর সাথে:

1. কোনো ε > 0-এর জন্য f(n) = O(n^{log_b a − ε}) হলে T(n) = Θ(n^{log_b a}).
2. f(n) = Θ(n^{log_b a}) হলে T(n) = Θ(n^{log_b a} log n).
3. কোনো ε > 0-এর জন্য f(n) = Ω(n^{log_b a + ε}), এবং কোনো c < 1-এর জন্য বড় n-এ a·f(n/b) ≤ c·f(n) (regularity শর্ত) হলে T(n) = Θ(f(n)).

প্রয়োগ:

• (ক) a = 9, b = 3: n^{log₃ 9} = n². f = n = O(n²⁻¹) → case ১ → Θ(n²).
• (খ) a = 1, b = 3/2: n⁰ = 1. f = 1 = Θ(1) → case ২ → Θ(log n).
• (গ) a = 3, b = 4: n^{log₄ 3} ≈ n^0.793. f = n log n = Ω(n^{0.793 + 0.2}); regularity: 3·(n/4)·log(n/4) ≤ (3/4)·n log n, c = 3/4 < 1 → case ৩ → Θ(n log n).
• (ঘ) a = 2, b = 2: n¹. f = n log n বড়, কিন্তু কোনো n^ε গুণ বড় নয় (log n < n^ε সব ε > 0-এর জন্য, বড় n-এ) — তিন case-এর কোনোটিই খাটে না। recursion tree-তে প্রতি তলা i-তে n·log(n/2ⁱ), যোগ করলে Θ(n log² n) (বর্ধিত case ২: f = Θ(n^{log_b a} log^k n) হলে Θ(n^{log_b a} log^k+1 n)).

নম্বর কোথায়: প্রতিটিতে a, b, n^{log_b a} লেখা; case ৩-এ regularity আলাদা করে যাচাই; আর (ঘ)-তে “খাটে না” বলার সাহস ও কারণ। পর্ব ০৯

অ্যালগরিদম: i = 0 থেকে n − 1 পর্যন্ত a[i] = x কি না দেখুন; পেলে i ফেরত দিন, না পেলে −1.

• Best case: x প্রথম ঘরে — ১টি তুলনা, Θ(1).
• Worst case: x শেষ ঘরে বা নেই — n টি তুলনা, Θ(n).
• Average case: ধরা যাক x আছে, আর n টি অবস্থানের প্রতিটি সমান সম্ভাব্য (1/n). অবস্থান k-তে (1-based) k টি তুলনা, তাই প্রত্যাশিত তুলনা = (1 + 2 + … + n)/n = (n + 1)/2 = Θ(n).

নম্বর কোথায়: average case-এ ইনপুটের অনুমান (“সমান সম্ভাব্য”) স্পষ্ট করা — অনুমান ছাড়া average-এর কোনো অর্থ নেই। জায়গা Θ(1). পর্ব ০৫

Pseudocode: POWER(x, n)        // n ≥ 0 integer
if n == 0: return 1
h = POWER(x, n div 2)          // one recursive call only
if n is even: return h * h
else:         return h * h * x

সঠিকতা (strong induction): n = 0-এ x⁰ = 1 ✓. ধরুন ⌊n/2⌋-এর জন্য h = x^⌊n/2⌋. n জোড় হলে h·h = xⁿ; বিজোড় হলে 2⌊n/2⌋ = n − 1, তাই h·h·x = xⁿ ✓.

Complexity: T(n) = T(⌊n/2⌋) + Θ(1) → Θ(log n) (master theorem case ২, বা প্রতি ডাকে n অর্ধেক)। n ≥ 1-এ ডাকের সংখ্যা ⌊log n⌋ + 2 (শেষ ডাকটি n = 0), প্রতিটিতে সর্বোচ্চ ২টি গুণ। call stack-এর জন্য জায়গা Θ(log n). সাধারণ ভুল: POWER(x, n/2) * POWER(x, n/2) লিখলে দুটি ডাক — T(n) = 2T(n/2) + 1 = Θ(n), সুবিধাই নষ্ট।

নম্বর কোথায়: base case, “একটিই রিকার্সিভ ডাক” আর বিজোড় n-এর বাড়তি x. পর্ব ০৭

মডেল: dynamic array-তে প্রতিটি push-এ একটি লেখা (খরচ 1). ভরা থাকলে নতুন দ্বিগুণ ব্লক নিয়ে পুরোনো সব উপাদান কপি করতে হয় (size টি কপি)। একটি push-এর worst case তাই Θ(n).

Aggregate প্রমাণ: ধারণক্ষমতা 1 থেকে শুরু। কপি হয় যখন size = 1, 2, 4, …, 2^k, যেখানে 2^k < n. মোট কপি = 1 + 2 + 4 + … + 2^k = 2^k+1 − 1 < 2n. লেখা n টি। তাই n টি push-এর মোট খরচ < n + 2n = 3n = O(n), গড়ে প্রতিটি O(1). ∎

Accounting দিয়ে একই কথা: প্রতিটি push থেকে ৩ টাকা নিন — ১ টাকায় নিজের লেখা, ২ টাকা জমা। ধারণক্ষমতা m থেকে 2m হওয়ার আগে শেষ m/2 টি push মোট m টাকা জমিয়েছে — ঠিক m টি কপির দাম। জমা কখনো ঋণাত্মক হয় না।

প্রতিবার +10: কপি হয় size = 10, 20, 30, … তে; মোট ≈ 10(1 + 2 + … + n/10) ≈ n²/20 = Θ(n²), তাই প্রতি push-এর amortized খরচ Θ(n). ধ্রুবক যোগ নয়, ধ্রুবক গুণ (growth factor > 1) দরকার।

নম্বর কোথায়: একক push-এর worst case Θ(n) আর amortized O(1) — দুটোই বলা; geometric series-এর যোগফল; আর amortized মানে “পুরো ক্রমের worst case-এর গড়”, সম্ভাবনা নয়। পর্ব ১০ · পর্ব ৬০

উপসংহার: বারবার index দিয়ে পড়া আর শেষে যোগ — array; মাঝখানে জানা জায়গায় অনেক যোগ-মোছা (যেমন LRU cache-এ hash map-এর সাথে) — linked list. বাস্তবে cache locality-র কারণে ছোট-মাঝারি n-এ array প্রায়ই জেতে।

নম্বর কোথায়: একই মাপকাঠিতে অন্তত ৫টি সারি, প্রতিটিতে নির্দিষ্ট complexity. পর্ব ১২

Pseudocode: REVERSE(head)
prev = NULL
cur  = head
while cur != NULL:
    nxt = cur.next       // save the rest of the list
    cur.next = prev      // turn this arrow around
    prev = cur
    cur = nxt
return prev              // new head

Trace: শুরুতে prev = NULL, cur = 1. ঘোরা ১: 1.next = NULL, prev = 1, cur = 2. ঘোরা ২: 2.next = 1, prev = 2, cur = 3. ঘোরা ৩: 3.next = 2, prev = 3, cur = NULL. ফেরত 3: তালিকা 3 → 2 → 1.

Invariant: প্রতিটি ঘোরার শুরুতে prev থেকে শুরু হওয়া তালিকা হলো মূল তালিকার ইতিমধ্যে দেখা অংশ, উল্টো ক্রমে। Complexity: প্রতিটি node একবার — Θ(n) সময়, Θ(1) বাড়তি জায়গা। খালি তালিকায় (head = NULL) লুপ চলে না, NULL ফেরত — সঠিক।

নম্বর কোথায়: nxt আগে বাঁচিয়ে রাখা (নইলে বাকি তালিকা হারায়), নতুন head ফেরত দেওয়া, খালি তালিকার কথা। পর্ব ১২

Pseudocode: BALANCED(s)
S = empty stack
for each ch in s:
    if ch is one of ( [ {: push(S, ch)
    else if ch is one of ) ] }:
        if S is empty or top(S) is not the match of ch: return false
        pop(S)
return S is empty

"([]{})": ( → [(]; [ → [( []; ] মেলে [ → [(]; { → [( {]; } মেলে { → [(]; ) মেলে ( → []. শেষে stack খালি → true.

"([)]": ( → [(]; [ → [( []; ) এলো, কিন্তু top = [ — মেলে না → false.

কেন stack: শেষে খোলা বন্ধনীটিকেই আগে বন্ধ করতে হয় — এটিই LIFO. Complexity: প্রতিটি অক্ষর একবার, প্রতিটি push/pop Θ(1) → Θ(n) সময়, worst case-এ Θ(n) জায়গা (সব খোলা বন্ধনী)।

নম্বর কোথায়: দুই রকম ব্যর্থতা — খালি stack-এ বন্ধ বন্ধনী, আর শেষে stack খালি না থাকা (যেমন "(("). শেষেরটি অনেকে ভুলে যান। পর্ব ১৩

Pseudocode: circular queue in Q[0..N-1], fields front, count
ENQUEUE(x):
    if count == N: error "full"
    Q[(front + count) mod N] = x
    count = count + 1
DEQUEUE():
    if count == 0: error "empty"
    x = Q[front]
    front = (front + 1) mod N
    count = count - 1
    return x

খালি/ভরা: শুধু front আর rear রাখলে দুই অবস্থাতেই front = rear হতে পারে — দ্ব্যর্থতা। সমাধান দুটি: (১) ওপরের মতো count রাখা — খালি count = 0, ভরা count = N; (২) একটি ঘর সবসময় খালি রাখা — খালি front = rear, ভরা (rear + 1) mod N = front; তখন N টি ঘরে সর্বোচ্চ N − 1টি উপাদান।

কেন circular: সাধারণ array-queue-তে dequeue-র পর সামনের ঘরগুলো নষ্ট হয়; mod N দিয়ে শেষ থেকে আবার শুরুতে ফেরা (wrap-around) সেই জায়গা ব্যবহার করে। প্রতিটি কাজ Θ(1).

নম্বর কোথায়: mod N, আর খালি-ভরার দ্ব্যর্থতা ও তার সমাধান। পর্ব ১৪

অ্যালগরিদম: দুটি stack — in আর out. enqueue(x): push(in, x). dequeue(): যদি out খালি হয়, in থেকে সব pop করে out-এ push করুন; তারপর pop(out).

কেন ঠিক: in থেকে out-এ ঢালার সময় ক্রম উল্টে যায়, তাই সবচেয়ে পুরোনো উপাদান out-এর মাথায় আসে — FIFO. out খালি না হলে ঢালা হয় না, তাই নতুন উপাদান পুরোনোদের আগে আসতে পারে না।

Amortized: প্রতিটি উপাদান জীবনে সর্বোচ্চ চারটি stack-কাজের মধ্য দিয়ে যায় — in-এ push, in থেকে pop, out-এ push, out থেকে pop. তাই n টি কাজের মোট খরচ ≤ 4n = O(n), প্রতিটি amortized O(1). একটি dequeue-র worst case অবশ্য Θ(n) — যখন n টি উপাদান একসাথে ঢালতে হয়।

উদাহরণ: enqueue 1, 2, 3 → in = [1, 2, 3]. dequeue: out খালি, তাই ঢালা → out = [3, 2, 1] (মাথায় 1), pop → 1. enqueue 4 → in = [4]. dequeue → 2 (ঢালা লাগেনি)।

নম্বর কোথায়: “out খালি হলেই কেবল ঢালা” শর্ত, আর প্রতি উপাদানে চারটি কাজের হিসাব। পর্ব ১৪ · পর্ব ৬০

Pseudocode: PAIR-SUM(a[0..n-1] sorted ascending, target)
i = 0;  j = n - 1
while i < j:
    s = a[i] + a[j]
    if s == target: return (i, j)
    if s < target:  i = i + 1
    else:           j = j - 1
return none

Invariant: যদি কোনো সমাধান জোড়া (p, q), p < q থাকে, তবে প্রতিটি ঘোরার শুরুতে i ≤ p আর q ≤ j — অর্থাৎ সমাধানটি এখনো জানালার ভেতরে।

রক্ষা: ধরুন s < target আর আমরা i বাড়াই। দেখাতে হবে i কোনো সমাধানের p নয়। i-এর যেকোনো সঙ্গী k থাকে i < k ≤ j-তে, আর অ্যারে সাজানো বলে a[k] ≤ a[j], তাই a[i] + a[k] ≤ a[i] + a[j] = s < target. সুতরাং i দিয়ে কোনো সমাধান নেই, ফেলে দেওয়া নিরাপদ। s > target-এ একই যুক্তিতে j ফেলা নিরাপদ। সমাপ্তি: প্রতি ঘোরায় j − i এক কমে, তাই সর্বোচ্চ n − 1 ঘোরায় থামে; সমাধান থাকলে জানালা তার আগে খালি হতে পারে না, তাই পাওয়া যাবেই। ∎

Complexity: Θ(n) সময়, Θ(1) জায়গা — দুই লুপের Θ(n²) brute force-এর তুলনায়। অসাজানো হলে আগে sort: O(n log n).

নম্বর কোথায়: “কেন একটি pointer সরানো নিরাপদ” — সাজানো ক্রম ব্যবহার করে অসমতাটি লেখা। শুধু “বড় হলে কমাই” লিখলে প্রমাণ হয় না। পর্ব ১৬

Pseudocode: BINARY-SEARCH(a[0..n-1] sorted, x)
lo = 0;  hi = n - 1
while lo <= hi:
    mid = lo + (hi - lo) div 2      // not (lo+hi)/2: avoids overflow
    if a[mid] == x: return mid
    if a[mid] < x:  lo = mid + 1
    else:           hi = mid - 1
return -1

Invariant: x যদি অ্যারেতে থাকে, তবে সেটি a[lo..hi]-তে আছে। শুরু: lo = 0, hi = n − 1 — পুরো অ্যারে ✓. রক্ষা: a[mid] < x হলে সাজানো ক্রমে a[0..mid]-এর সবাই < x, তাই x থাকলে a[mid+1..hi]-তে ✓; উল্টো দিকও একইভাবে। সমাপ্তি: lo > hi হলে জানালা খালি — invariant বলছে x নেই, −1 সঠিক। প্রতি ঘোরায় জানালার আকার hi − lo + 1 অন্তত অর্ধেক হয়, তাই থামে।

Complexity: জানালা n → ≤ n/2 → ≤ n/4 …, তাই ঘোরা সর্বোচ্চ ⌊log n⌋ + 1 → Θ(log n) worst case, Θ(1) best case, Θ(1) জায়গা।

নম্বর কোথায়: lo ≤ hi শর্ত (< লিখলে এক-উপাদানের জানালা বাদ পড়ে — off-by-one), mid ± 1 (না দিলে অসীম লুপ হতে পারে), আর পূর্বশর্ত “অ্যারে সাজানো”. পর্ব ১৮

Pseudocode: MERGE-SORT(a, lo, hi)     // sorts a[lo..hi-1]
if hi - lo < 2: return
mid = lo + (hi - lo) div 2
MERGE-SORT(a, lo, mid)
MERGE-SORT(a, mid, hi)
MERGE(a, lo, mid, hi)    // two sorted halves -> one, using a buffer;
                         // on a tie take the LEFT item first

Recurrence: দুই অর্ধেক + merge-এ সর্বোচ্চ n − 1টি তুলনা: T(n) = 2T(n/2) + Θ(n) → ক-০৫-এর মতো Θ(n log n) — best, worst, average তিনটিতেই, কারণ ইনপুট যেমনই হোক ভাগ একই রকম।

Stable: হ্যাঁ, যদি সমান হলে বাঁ দিকেরটা আগে নেওয়া হয় (≤). In-place: না — merge-এর জন্য Θ(n) বাড়তি জায়গা, সাথে Θ(log n) call stack.

নম্বর কোথায়: base case (আকার < 2), merge-এর বর্ণনা, recurrence থেকে Θ(n log n), আর stability-র শর্ত “≤”. পর্ব ২১

Worst case: pivot প্রতিবার সবচেয়ে ছোট বা বড় হলে (যেমন সাজানো ইনপুটে শেষ উপাদান pivot, Lomuto) এক পাশে n − 1, অন্য পাশে 0: T(n) = T(n − 1) + Θ(n) → Θ(n²). Best: প্রতিবার মাঝামাঝি ভাগ: T(n) = 2T(n/2) + Θ(n) → Θ(n log n). এমনকি প্রতিবার 1:9 ভাগ হলেও গভীরতা log_10/9 n = Θ(log n), মোট Θ(n log n).

Randomized — প্রত্যাশিত তুলনা: সাজানো ক্রমে উপাদানগুলো z₁ < z₂ < … < z_n. z_i আর z_j (i < j) তুলনা হয় কেবল যদি {z_i, …, z_j}-এর মধ্যে প্রথম যে pivot বাছা হয়, সেটি z_i বা z_j — নইলে মাঝের pivot তাদের আলাদা দুই পাশে পাঠিয়ে দেয়। pivot এলোমেলো, তাই সম্ভাবনা 2/(j − i + 1). Linearity of expectation দিয়ে:

আরও নিখুঁতভাবে প্রায় 2n ln n ≈ 1.39 n log n. এটি সব ইনপুটের জন্য — খারাপ ইনপুট বলে কিছু নেই, শুধু দুর্ভাগ্য, যার সম্ভাবনা খুব কম।

নম্বর কোথায়: worst case কোন ইনপুটে আর কেন; randomized বিশ্লেষণে “প্রথম pivot” যুক্তি আর 2/(j − i + 1). জায়গা: in-place, গড়ে Θ(log n) stack; ছোট পাশে আগে রিকার্শন করলে worst case-এও O(log n). পর্ব ২২ · পর্ব ৬১

Pseudocode: BUILD-MAX-HEAP(a[0..n-1])
for i = n div 2 - 1 down to 0:
    SIFT-DOWN(a, i, n)    // swap with larger child until heap property holds

মূল ধারণা: sift-down-এর খরচ node-এর উচ্চতার সমানুপাতিক, গভীরতার নয়। আর বেশিরভাগ node নিচের দিকে, যাদের উচ্চতা ছোট। n node-এর heap-এ উচ্চতা h-এর node সর্বোচ্চ ⌈n/2^h+1⌉ টি।

কারণ Σ_h≥0 h/2^h = 2 (একটি অভিসারী ধারা)। ∎ “n/2 টি node × O(log n) = O(n log n)” একটি সত্য কিন্তু ঢিলে সীমা — প্রশ্নে আঁটসাঁট সীমা চাওয়া হয়েছে।

উদাহরণ: n = 15 (পূর্ণ tree, উচ্চতা 3): ৮টি পাতা (উচ্চতা 0), ৪টি উচ্চতা 1, ২টি উচ্চতা 2, ১টি উচ্চতা 3. swap সর্বোচ্চ 4·1 + 2·2 + 1·3 = 11 < n. সাধারণভাবে পূর্ণ tree-তে সব উচ্চতার যোগফল n − (উচ্চতা + 1). ছোট্ট একটি পরীক্ষায় ঊর্ধ্বক্রমে সাজানো ইনপুট (max-heap-এর জন্য সবচেয়ে খারাপ) n = 1023-এ ঠিক 1013টি swap দিয়েছে = 1023 − 10.

নম্বর কোথায়: উচ্চতা অনুযায়ী node গোনা, ধারার যোগফল 2, আর “n log n ঢিলে” মন্তব্য। এর ফলেই heapsort-এর প্রথম ধাপ O(n), যদিও মোট heapsort Θ(n log n). পর্ব ২৩

মডেল: তুলনা-ভিত্তিক সর্ট উপাদান সম্পর্কে শুধু “a_i ≤ a_j?” প্রশ্ন করে তথ্য পায়। নির্দিষ্ট n-এর জন্য এমন অ্যালগরিদমকে একটি decision tree হিসেবে আঁকা যায়: প্রতিটি ভেতরের node একটি তুলনা, দুই শাখা দুই উত্তর, প্রতিটি পাতা একটি চূড়ান্ত বিন্যাস (permutation). একটি ইনপুটে অ্যালগরিদম মূল থেকে একটি পাতা পর্যন্ত একটি পথ ধরে; worst case-এর তুলনার সংখ্যা = tree-র উচ্চতা h.

প্রমাণ:

1. n টি ভিন্ন উপাদানের n! টি বিন্যাস সম্ভব, আর প্রতিটির জন্য আলাদা উত্তর দরকার — দুটি ভিন্ন ইনপুট একই পাতায় এলে অন্তত একটি ভুল সাজানো হবে। তাই পাতা ≥ n!.
2. উচ্চতা h-এর binary tree-তে পাতা সর্বোচ্চ 2^h. তাই 2^h ≥ n!, অর্থাৎ h ≥ log(n!).
3. n! ≥ (n/2)^n/2 (শেষ n/2 টি গুণফলের প্রতিটি ≥ n/2), তাই log(n!) ≥ (n/2)·log(n/2) = Ω(n log n). ∎

উদাহরণ: n = 3: 3! = 6 টি পাতা, ⌈log 6⌉ = 3 — তিনটি উপাদান দুই তুলনায় সব সময় সাজানো অসম্ভব। উপসংহার: merge sort আর heapsort তাই asymptotically সেরা তুলনা-সর্ট। counting বা radix sort এই সীমা “ভাঙে” না — তারা তুলনা ছাড়াও কী-এর অঙ্ক দেখে, তাই এই মডেলের বাইরে।

নম্বর কোথায়: decision tree-র সংজ্ঞা, পাতা ≥ n! কেন, 2^h ≥ পাতা, আর log(n!)-এর নিম্নসীমা (Stirling বা ওপরের সরল যুক্তি)। পর্ব ২৪

Counting sort: কী-গুলো 0..k-এর পূর্ণসংখ্যা। (১) cnt[v] = v কতবার আছে; (২) prefix sum: cnt[v] = ≤ v কী-এর সংখ্যা; (৩) ইনপুট ডান থেকে বাঁয়ে পড়ে প্রতিটি x-কে out[cnt[x] − 1]-এ বসান, cnt[x] এক কমান। সময় Θ(n + k), জায়গা Θ(n + k).

Stable: সমান কী-এর উপাদানগুলোর আগের আপেক্ষিক ক্রম অপরিবর্তিত থাকে। ধাপ (৩)-এ ডান থেকে পড়া এটিই নিশ্চিত করে।

LSD radix: d অঙ্কের সংখ্যা, প্রথমে একক অঙ্ক ধরে stable sort, তারপর দশক, … শেষে সবচেয়ে বড় অঙ্ক। Invariant: i টি পাস শেষে সংখ্যাগুলো শেষ i টি অঙ্ক ধরে সাজানো। পরের পাসে যাদের নতুন অঙ্ক সমান, stability তাদের আগের (নিচের অঙ্কের) ক্রম রাখে — stable না হলে আগের পাসের কাজ নষ্ট। উদাহরণ: 21, 12 → একক ধরে: 21, 12; দশক ধরে: 12, 21 ✓. সময় Θ(d(n + b)), b = ভিত্তি।

নম্বর কোথায়: তিন ধাপ, ডান থেকে পড়ার কারণ, invariant, আর “k বড় হলে (যেমন k = n²) counting sort অচল”. পর্ব ২৪ · পর্ব ২৫

BST-এর নিয়ম: প্রতিটি node-এর বাঁ subtree-র সব key ছোট, ডানের সব বড়। মোছার পরেও এটি রাখতে হবে।

1. পাতা: সরাসরি মুছে দিন — মা-বাবার pointer NULL.
2. একটি সন্তান: node-টিকে তার একমাত্র সন্তান দিয়ে প্রতিস্থাপন করুন (মা-বাবা এখন নাতিকে দেখায়)।
3. দুটি সন্তান: ডান subtree-র সবচেয়ে ছোট node — inorder successor s — খুঁজুন। s-এর key এই node-এ কপি করুন, তারপর s-কে মুছুন। s-এর বাঁ সন্তান থাকতে পারে না (থাকলে সেটিই আরও ছোট হতো), তাই s মোছা case ১ বা ২.

কেন নিয়ম টেকে: successor বাঁ subtree-র সবার চেয়ে বড় আর ডানের বাকি সবার চেয়ে ছোট — তাই ওই জায়গায় বসার যোগ্য। Complexity: খোঁজা আর successor মিলিয়ে O(h), h = উচ্চতা: ভারসাম্যপূর্ণ হলে O(log n), একপাশে হেলে পড়লে O(n).

নম্বর কোথায়: তিন case, case ৩-এ successor-এর “বাঁ সন্তান নেই” যুক্তি, আর O(h) — O(log n) নয়, যদি না balance-এর কথা বলা হয়। পর্ব ২৭

নিয়ম: AVL tree-তে প্রতিটি node-এর দুই subtree-র উচ্চতার পার্থক্য (balance factor) সর্বোচ্চ 1. উচ্চতা গোনা হচ্ছে edge-এ — একটি node-এর tree-র উচ্চতা 0.

ধাপ ১ — সবচেয়ে কম node: উচ্চতা h-এর AVL tree-তে সর্বনিম্ন node-সংখ্যা N(h). সবচেয়ে “পাতলা” tree-তে মূলের এক subtree উচ্চতা h − 1, অন্যটি h − 2 (পার্থক্য 1-এর বেশি হতে পারে না), আর দুটিও সর্বনিম্ন:

মানগুলো: 1, 2, 4, 7, 12, 20, 33, 54, …

ধাপ ২ — সূচকীয় বৃদ্ধি (সরল সংস্করণ): N(h) > 2·N(h − 2), কারণ N(h − 1) ≥ N(h − 2). বারবার প্রয়োগে N(h) > 2^h/2 (h ≥ 2-এ; base N(0) = 1, N(1) = 2 মিলিয়ে নিন)। তাই n ≥ N(h) > 2^h/2, অর্থাৎ h < 2 log n = O(log n). ∎

আঁটসাঁট সংস্করণ: N(h) + 1 = F(h + 3), Fibonacci সংখ্যা (2, 3, 5, 8, 13, …)। F(m) ≥ φ^m−2, φ ≈ 1.618, তাই n + 1 ≥ φ^h+1, আর h < 1.44 log(n + 2). অর্থাৎ AVL সবচেয়ে খারাপ অবস্থায়ও নিখুঁত tree-র চেয়ে মোটামুটি ৪৪% বেশি উঁচু।

নম্বর কোথায়: N(h)-এর recurrence আর কেন দুই subtree h − 1 ও h − 2, base case, আর অসমতা থেকে log-এ যাওয়া। পর্ব ২৮

মডেল: m টি bucket, n টি key, প্রতিটি bucket একটি তালিকা (separate chaining). Load factor α = n/m — গড়ে একটি তালিকার দৈর্ঘ্য।

প্রত্যাশিত: simple uniform hashing-এর অনুমানে (প্রতিটি key স্বাধীনভাবে যেকোনো bucket-এ সমান সম্ভাবনায়) একটি তালিকার প্রত্যাশিত দৈর্ঘ্য α. ব্যর্থ খোঁজায় hash হিসাব + পুরো তালিকা: Θ(1 + α). সফল খোঁজাতেও Θ(1 + α).

Worst case: সব n key একই bucket-এ গেলে খোঁজা Θ(n). এটি ঘটে দুর্বল hash function-এ, বা কেউ ইচ্ছা করে সংঘর্ষ ঘটানো key পাঠালে (hash flooding).

Rehash: n বাড়লে α বাড়ে, খোঁজা ধীর হয়। α একটি সীমা (যেমন 1) পেরোলে m দ্বিগুণ করে সব key নতুন table-এ বসানো হয় — একবারে Θ(n), কিন্তু খ-০১-এর মতো amortized O(1). তাই α = O(1) রাখলে insert, search, delete প্রত্যাশিত O(1).

নম্বর কোথায়: অনুমানটি স্পষ্ট করা (প্রত্যাশিত O(1) কোনো শর্তহীন সত্য নয়), Θ(1 + α), আর worst case-এর কারণ। পর্ব ৩২

Union by rank: দুই মূলের মধ্যে ছোট rank-এর মূলকে বড়টির নিচে বসান; সমান হলে যেকোনো একটিকে নিচে দিয়ে অন্যটির rank এক বাড়ান।

দাবি: rank r-এর মূলের tree-তে অন্তত 2^r টি node. Induction: r = 0-এ একটি node ✓. rank r + 1 হয় কেবল দুটি rank-r মূল জোড়া লাগলে — প্রতিটিতে ≥ 2^r, মোট ≥ 2^r+1 ✓. অসমান rank-এ জোড়া লাগলে rank বাড়ে না, node শুধু বাড়ে ✓. তাই 2^r ≤ n, r ≤ log n. tree-র উচ্চতা ≤ rank, তাই find O(log n). ∎

Path compression: find-এর পথে পাওয়া প্রতিটি node-কে সরাসরি মূলের সাথে জুড়ে দেয়। দুটি একসাথে থাকলে m টি কাজের মোট খরচ O(m·α(n)) — inverse Ackermann α(n), যা বাস্তবের যেকোনো n-এ ৪-এর বেশি নয় (Tarjan, ১৯৭৫)। তাই প্রতি কাজ amortized “প্রায় ধ্রুবক”.

নম্বর কোথায়: 2^r দাবির induction, আর α(n) amortized — worst case প্রতি কাজে নয়। পর্ব ৩৩

সংজ্ঞা: minimum degree t ≥ 2-এর B-tree-তে মূল ছাড়া প্রতিটি node-এ t − 1 থেকে 2t − 1 টি key সাজানো থাকে, k টি key-এর node-এর k + 1 টি সন্তান, আর সব পাতা একই গভীরতায়।

উচ্চতা: n ≥ 1 key-এ h ≤ log_t((n + 1)/2). কারণ গভীরতা 1-এ অন্তত 2টি node, তারপর প্রতি স্তরে অন্তত t গুণ, প্রতিটিতে অন্তত t − 1 key: n ≥ 1 + 2(t − 1)(1 + t + … + t^h−1) = 2t^h − 1.

কেন ডিস্কে: ডিস্ক বা SSD থেকে একটি ব্লক আনা মেমরির একটি তুলনার চেয়ে বহু গুণ ধীর। B-tree-র একটি node = একটি ব্লক, তাই খরচ গোনা হয় ব্লক পড়ায়, আর তা উচ্চতার সমান। t = 1000 হলে 10⁹ key-এ h ≤ log₁₀₀₀(5 × 10⁸) ≈ 2.9, অর্থাৎ উচ্চতা ২ — মাত্র ৩ স্তর, মূল মেমরিতে রাখলে ২টি ব্লক পড়া। binary BST-তে উচ্চতা কমপক্ষে প্রায় 30.

নম্বর কোথায়: key-সংখ্যার সীমা, সব পাতা এক গভীরতায়, উচ্চতার সূত্র, আর ব্লক-পড়াকে খরচ ধরার যুক্তি। পর্ব ৩০

গঠন: segment tree-র প্রতিটি node একটি অংশ [l, r]-এর উত্তর (যেমন যোগফল বা min) রাখে; সন্তানেরা অংশটি দুই ভাগ করে। উচ্চতা ⌈log n⌉.

Query [L, R]: একটি node-এর অংশ পুরো ভেতরে হলে তার মান নিন; পুরো বাইরে হলে বাদ দিন; আংশিক মিললে দুই সন্তানে যান।

দাবি: প্রতিটি স্তরে সর্বোচ্চ ২টি node “আংশিক” — যাদের থেকে নিচে যাওয়া হয়। যুক্তি: এক স্তরের অংশগুলো পাশাপাশি, পরস্পর আলাদা। [L, R]-এর সাথে আংশিক মিল হতে পারে কেবল যে node-এ L বা R সীমানাটি পড়েছে — বড়জোর দুটি; মাঝের সবাই পুরো ভেতরে। তাই প্রতি স্তরে সর্বোচ্চ ২টি node বিস্তারিত হয়, ঘোরা হয় ≤ 4টি node-এ; স্তর ⌈log n⌉ + 1, মোট O(log n). ∎

অন্যগুলো: build Θ(n) (প্রায় 2n − 1 টি node, প্রতিটি একবার); point update O(log n) (পাতা থেকে মূল পর্যন্ত এক পথ); জায়গা Θ(n) (array-তে সাধারণত 4n ঘর রাখা হয়)। range update-এর জন্য lazy propagation লাগে, তখনও O(log n).

নম্বর কোথায়: “প্রতি স্তরে ≤ 2টি আংশিক node” — এটিই প্রমাণের মূল; শুধু “উচ্চতা log n” বললে যথেষ্ট নয়। পর্ব ৩৪ · পর্ব ৩৫

অ্যালগরিদম: BFS উৎস s-কে dist 0 দিয়ে queue-তে রাখে; queue থেকে u বের করে প্রতিটি অদেখা প্রতিবেশী v-কে dist[v] = dist[u] + 1 দিয়ে queue-তে ঢোকায়।

Lemma (queue-এর গঠন): যেকোনো মুহূর্তে queue-তে dist-এর মান সামনে থেকে পেছনে অ-হ্রাসমান, আর শেষের মান ≤ প্রথমের মান + 1. (u বের হয়ে dist[u] + 1-এর vertex পেছনে যোগ হয় — দুই শর্তই টিকে থাকে।) ফলে vertex-গুলো queue থেকে বের হয় dist-এর অ-হ্রাসমান ক্রমে।

প্রমাণ (δ(v)-এর ওপর induction, δ = আসল দূরত্ব): δ = 0: শুধু s, dist 0 ✓. ধরুন δ ≤ k-এর সব vertex সঠিক dist পেয়েছে। δ(v) = k + 1 হলে v-এর একটি প্রতিবেশী u আছে যার δ(u) = k. dist[v] ≥ k + 1, কারণ dist সবসময় একটি আসল পথের দৈর্ঘ্য। আবার lemma অনুযায়ী dist ≤ k-এর সব vertex dist = k + 1-এর কোনো vertex-এর আগে বের হয়; তাই u বের হওয়ার সময় v-কে কেউ আগে আবিষ্কার করে থাকলে তার dist ≤ k + 1, নইলে u নিজেই দেবে dist[u] + 1 = k + 1. দুই ক্ষেত্রেই dist[v] = k + 1 ✓. ∎

Complexity: adjacency list-এ প্রতিটি vertex একবার queue-তে, প্রতিটি edge সর্বোচ্চ দুবার দেখা: Θ(V + E) সময়, Θ(V) বাড়তি জায়গা। adjacency matrix-এ Θ(V²).

নম্বর কোথায়: queue-এর lemma, “dist একটি আসল পথ, তাই ≥ δ” আর induction-এর ধাপ। weighted গ্রাফে BFS কেন চলে না — এক লাইনে যোগ করুন। পর্ব ৪০

সংজ্ঞা: Topological order হলো vertex-গুলোর এমন সারি, যেখানে প্রতিটি edge u → v-তে u আগে আসে। DAG = cycle নেই এমন directed graph.

(⇒) order আছে ⇒ cycle নেই: ধরুন cycle v₁ → v₂ → … → v_k → v₁ আছে। order-এ প্রতিটি edge সামনে যায়, তাই pos(v₁) < pos(v₂) < … < pos(v_k) < pos(v₁) — অসম্ভব।

(⇐) DAG ⇒ order আছে: প্রথমে দাবি: DAG-এ in-degree 0-এর একটি vertex আছে। নইলে যেকোনো vertex থেকে আসা-edge ধরে পেছনে হাঁটা যেত অনন্তকাল; V ধাপ হাঁটলে V + 1টি vertex পেরোতে হয়, অথচ vertex আছে V টি — তাই কোনো vertex দুবার আসে — একটি cycle, বিরোধ। সেই vertex-টি প্রথমে বসান, তাকে মুছুন; বাকিটা এখনো DAG (vertex মুছলে cycle তৈরি হয় না)। V-এর ওপর induction-এ বাকিটার order আছে; সামনে বসালে পুরো order পাওয়া যায়। ∎

Pseudocode: KAHN(G)
compute indeg[v] for all v
Q = all v with indeg[v] == 0
order = []
while Q not empty:
    u = Q.pop();  order.append(u)
    for each edge u -> v:
        indeg[v] = indeg[v] - 1
        if indeg[v] == 0: Q.push(v)
if len(order) < V: report "cycle"      // not a DAG
return order

Complexity: Θ(V + E). প্রমাণের (⇐) অংশটিই এই অ্যালগরিদম — তাই order ছোট হলে নিশ্চিতভাবে cycle আছে।

নম্বর কোথায়: দুই দিক আলাদা করে, in-degree 0-এর অস্তিত্বের যুক্তি, আর cycle শনাক্তের শর্ত। পর্ব ৪২

অ্যালগরিদম: Dijkstra প্রতিবার অমীমাংসিত vertex-গুলোর মধ্যে সবচেয়ে ছোট d[u]-এর u-কে “settled” করে, তারপর u-এর বাইরের edge-গুলো relax করে: d[v] = min(d[v], d[u] + w(u, v)).

দাবি: u settled হওয়ার মুহূর্তে d[u] = δ(s, u). (d সবসময় কোনো আসল পথের দৈর্ঘ্য, তাই d[u] ≥ δ(u).)

প্রমাণ (contradiction): ধরুন u হলো প্রথম vertex যা settle হলো d[u] > δ(u) নিয়ে। s → u-এর একটি সবচেয়ে ছোট পথ P নিন। P-তে প্রথম অমীমাংসিত vertex y, আর তার আগেরটি x (settled; s নিজে settled বলে x আছে)। u প্রথম ভুল, তাই d[x] = δ(x); x settle হওয়ার সময় x → y relax হয়েছে, তাই d[y] ≤ δ(x) + w(x, y) = δ(y). এখন weight অ-ঋণাত্মক বলে P-তে y থেকে u পর্যন্ত বাকি অংশের দৈর্ঘ্য ≥ 0, তাই δ(y) ≤ δ(u). মিলিয়ে: d[y] ≤ δ(y) ≤ δ(u) < d[u]. কিন্তু Dijkstra u-কে বেছেছে সবচেয়ে ছোট d হিসেবে, অথচ y-ও অমীমাংসিত ছিল — তাই d[u] ≤ d[y]. বিরোধ। ∎

ঋণাত্মক edge: প্রমাণের যে লাইনে δ(y) ≤ δ(u) লেগেছে, সেটি ঋণাত্মক edge-এ ভাঙে — একটি settled vertex-এর দূরত্ব পরে আরও কমতে পারে। নিচের ডায়াগ্রাম আর প্রোগ্রামে উদাহরণ: S → A (2), S → B (5), A → C (1), B → A (−4). আসল দূরত্ব A = 1 (S → B → A), C = 2; Dijkstra দেয় A = 2, C = 3.

Complexity: binary heap-এ O((V + E) log V); array-তে min খুঁজলে Θ(V²) — ঘন গ্রাফে এটিই ভালো।

নম্বর কোথায়: “প্রথম ভুল vertex” কাঠামো, x আর y-এর সংজ্ঞা, ঠিক কোন লাইনে অ-ঋণাত্মকতা লাগল, আর একটি নির্দিষ্ট পাল্টা-উদাহরণ (counterexample). পর্ব ৪৩

অ্যালগরিদম: Bellman-Ford d[s] = 0, বাকি ∞; তারপর V − 1 বার সব E টি edge relax করে।

Lemma: i টি রাউন্ড শেষে প্রতিটি v-এর জন্য d[v] ≤ সর্বোচ্চ i টি edge-এর s → v পথগুলোর মধ্যে সবচেয়ে ছোটটির দৈর্ঘ্য। Induction: i = 0-এ শুধু s, 0 ✓. ধরুন i − 1-এ সত্য। ≤ i edge-এর সেরা পথের শেষ edge u → v; পথের বাকিটা ≤ i − 1 edge, তাই d[u] ইতিমধ্যে ততটা ছোট; রাউন্ড i-তে u → v relax হলে d[v] ≤ d[u] + w ✓.

কেন V − 1: ঋণাত্মক cycle না থাকলে একটি সবচেয়ে ছোট পথ simple ধরা যায় (cycle-এর weight ≥ 0, তাই বাদ দিলে পথ লম্বা হয় না), আর simple পথে সর্বোচ্চ V − 1 টি edge. lemma অনুযায়ী V − 1 রাউন্ড শেষে d[v] ≤ δ(v); আর d সবসময় একটি আসল পথ, তাই d[v] = δ(v). ∎

শনাক্তকরণ: আরও একটি রাউন্ড চালান। কোনো edge-এ তখনো d[u] + w < d[v] হলে s থেকে পৌঁছানো যায় এমন একটি negative cycle আছে — কারণ না থাকলে ওপরের প্রমাণ বলে সব d ইতিমধ্যে চূড়ান্ত।

Complexity: Θ(V·E) সময়, Θ(V) জায়গা। কোনো রাউন্ডে কিছু না বদলালে আগেই থামানো যায়। ওপরের প্রোগ্রামে ৪টি vertex, তাই ৩ রাউন্ড।

নম্বর কোথায়: lemma-র নির্ভুল বিবৃতি (“≤ i edge-এর পথ”), simple path-এ V − 1 edge, আর V-তম রাউন্ডের যুক্তি। পর্ব ৪৪

সংজ্ঞা: একটি cut (S, V − S) হলো vertex-গুলোর দুই ভাগ; যে edge-এর দুই প্রান্ত দুই ভাগে, সেটি cut-কে অতিক্রম করে (crossing edge).

Cut property: ধরুন A কোনো একটি MST-র edge-এর উপসেট, আর cut (S, V − S)-কে A-র কোনো edge অতিক্রম করে না। তাহলে cut অতিক্রমকারী সবচেয়ে হালকা edge e = (u, v) যোগ করলে A ∪ {e}-ও কোনো MST-র উপসেট।

প্রমাণ (exchange): T একটি MST, A ⊆ T. e ∈ T হলে শেষ। নইলে T ∪ {e}-তে ঠিক একটি cycle তৈরি হয়, যাতে আছে u থেকে v-এর T-পথ। u আর v দুই ভাগে, তাই এই পথ অন্তত আরেকবার cut অতিক্রম করে — একটি edge e′ দিয়ে। e′ ∉ A (A cut অতিক্রম করে না)। T′ = T − {e′} + {e} আবার একটি spanning tree (cycle ভাঙল, সংযোগ রইল)। e সবচেয়ে হালকা, তাই w(e) ≤ w(e′), আর w(T′) ≤ w(T). T নিজে minimum, তাই T′-ও MST, এবং A ∪ {e} ⊆ T′. ∎

Kruskal: edge-গুলো weight-এর ক্রমে দেখে; যে edge দুটি আলাদা component জোড়ে তা নেয়। নেওয়া edge (u, v)-এর জন্য S = u-এর বর্তমান component নিন: আগের কোনো নেওয়া edge এই cut অতিক্রম করে না, আর এর চেয়ে হালকা কোনো crossing edge থাকলে সেটি আগেই দেখা হতো এবং নেওয়া হতো। তাই এটি সবচেয়ে হালকা crossing edge — cut property অনুযায়ী নিরাপদ। V − 1টি নিরাপদ edge = একটি MST. complexity O(E log E) = O(E log V) (sort + DSU).

নম্বর কোথায়: cut property-র তিনটি শর্ত (A ⊆ MST, A cut মানে, e সবচেয়ে হালকা), cycle-এ দ্বিতীয় crossing edge e′-এর অস্তিত্ব, আর Kruskal-এ cut-টি কী তা স্পষ্ট বলা। পর্ব ৪৫

বিবৃতি: যেকোনো flow network-এ উৎস s থেকে গন্তব্য t-এর সর্বোচ্চ flow-এর মান = সব s-t cut-এর মধ্যে সবচেয়ে ছোট capacity. সমতুল্যভাবে, একটি flow f-এর জন্য এই তিনটি একই কথা: (১) f সর্বোচ্চ; (২) residual graph-এ কোনো augmenting path নেই; (৩) কোনো cut (S, T)-এর জন্য |f| = c(S, T).

মূল যুক্তি: যেকোনো flow ≤ যেকোনো cut, কারণ s থেকে t-এ যাওয়া সব flow-কে cut পেরোতে হয় (weak duality). augmenting path না থাকলে S = residual graph-এ s থেকে পৌঁছানো যায় এমন vertex নিন: S থেকে বের হওয়া প্রতিটি edge পুরো ভরা, আর ঢোকা প্রতিটি edge-এ flow 0 — তাই |f| = c(S, T), আর f সর্বোচ্চ।

Pseudocode: FORD-FULKERSON(G, s, t)
f = 0 on every edge
while there is an s-t path p in the residual graph:
    b = minimum residual capacity on p      // bottleneck
    push b units along p (update forward and reverse edges)
return f

উদাহরণ: s → a (4), s → b (2), a → b (3), a → t (1), b → t (4). flow: s → a 4 (তার 1 যায় a → t, 3 যায় a → b), s → b 1, b → t 4. মান 1 + 4 = 5. cut S = {s, a, b}: বের হয় a → t (1) + b → t (4) = 5. flow = cut, তাই দুটিই সেরা — আর কোনো augmenting path নেই।

Complexity: পূর্ণসংখ্যার capacity-তে প্রতি augment-এ ≥ 1 বাড়ে: O(E·|f*|). BFS দিয়ে সবচেয়ে ছোট পথ নিলে (Edmonds-Karp) O(V·E²), capacity যা-ই হোক।

নম্বর কোথায়: তিন শর্তের সমতুল্যতা, residual graph-এ reverse edge-এর কথা, আর উদাহরণে flow ও cut দুটোই দেখানো। পর্ব ৪৭

সমস্যা: n টি কাজ, প্রতিটির শুরু s আর শেষ f. পরস্পর না-মেলা (একটি শেষ হওয়ার পর অন্যটি শুরু) সবচেয়ে বেশি কাজ বাছতে হবে — যেমন একটি হলরুমে সবচেয়ে বেশি অনুষ্ঠান।

Greedy: f অনুযায়ী সাজান; প্রথমটি নিন; তারপর প্রতিটি কাজ নিন যার s ≥ শেষ নেওয়া কাজের f.

প্রমাণ (exchange argument): g₁ = সবচেয়ে আগে শেষ হওয়া কাজ। যেকোনো সেরা সমাধান O নিন, শেষের ক্রমে o₁, o₂, …, o_k. o₁-এর জায়গায় g₁ বসান: f(g₁) ≤ f(o₁) ≤ s(o₂), তাই g₁ বাকিদের সাথে মেলে না, আর সংখ্যা এখনো k. অর্থাৎ g₁-সহ একটি সেরা সমাধান আছে (greedy-choice property). g₁ নেওয়ার পর বাকি সমস্যা হলো “f(g₁)-এর পর শুরু হওয়া কাজগুলো” — একই ধরনের ছোট সমস্যা, আর তার সেরা সমাধান + g₁ = পুরোটার সেরা (optimal substructure). k-এর ওপর induction-এ greedy সেরা। ∎

উদাহরণ: (s, f) = (1,4), (3,5), (0,6), (5,7), (3,9), (5,9), (6,10), (8,11), (8,12), (2,14), (12,16). greedy নেয় (1,4), (5,7), (8,11), (12,16) — ৪টি।

Complexity: sort O(n log n) + এক পাস O(n). সতর্কতা: “সবচেয়ে ছোট কাজ আগে” বা “সবচেয়ে আগে শুরু” greedy ভুল — একটি করে পাল্টা-উদাহরণ খুঁজে দেখুন।

নম্বর কোথায়: বদলানোর পরও সমাধান বৈধ — f(g₁) ≤ f(o₁) ≤ s(o₂) অসমতাটি; আর সংখ্যা কমেনি। পর্ব ৫০

অ্যালগরিদম: প্রতিটি অক্ষর একটি পাতা, একটি min-heap-এ। বারবার সবচেয়ে কম ফ্রিকোয়েন্সির দুটি বের করে জোড়া লাগান (নতুন node-এর ফ্রিকোয়েন্সি = যোগফল), heap-এ ফেরত দিন — যতক্ষণ না একটি tree থাকে।

Trace: 5 + 9 = 14 → 12 + 13 = 25 → 14 + 16 = 30 → 25 + 30 = 55 → 45 + 55 = 100. কোডের দৈর্ঘ্য: f = 1, c = d = e = 3, a = b = 4 বিট; যেমন f = 0, c = 100, d = 101, a = 1100, b = 1101, e = 111 (বাঁ = 0, ডান = 1 ধরে)।

৬টি অক্ষরের জন্য নির্দিষ্ট দৈর্ঘ্যের কোডে লাগত ৩ বিট × ১০০ = ৩০০ বিট। কোনো কোড অন্যটির শুরু নয় (prefix-free), তাই পড়ার সময় দ্ব্যর্থতা নেই।

সেরা কেন (স্কেচ): (১) Greedy choice: সবচেয়ে কম ফ্রিকোয়েন্সির দুই অক্ষর x, y-কে সবচেয়ে গভীর স্তরে ভাই বানানো এমন একটি সেরা tree আছে — যেকোনো সেরা tree-র সবচেয়ে গভীর দুই ভাই-পাতার সাথে x, y অদলবদল করলে খরচ বাড়ে না (কম ফ্রিকোয়েন্সি গভীরে গেল)। (২) Optimal substructure: x, y-কে একটি নতুন অক্ষর z (f = f_x + f_y) দিয়ে বদলালে B(T) = B(T′) + f_x + f_y, তাই ছোট সমস্যার সেরা tree থেকে বড়টির সেরা tree পাওয়া যায়। অক্ষর-সংখ্যার ওপর induction. ∎

Complexity: n অক্ষরে O(n log n) (heap-এ n − 1 বার merge).

নম্বর কোথায়: প্রতিটি merge-এর ক্রম, tree-র ছবি, প্রতিটি কোড ও তার দৈর্ঘ্য, মোট বিট, আর দুই lemma-র নাম। পর্ব ৫১

State: L[i][j] = X-এর প্রথম i অক্ষর আর Y-এর প্রথম j অক্ষরের LCS-এর দৈর্ঘ্য।

কেন ঠিক: শেষ দুই অক্ষর মিললে কোনো একটি LCS সেটি দিয়েই শেষ হয় (exchange); না মিললে LCS-এ অন্তত একটি শেষ অক্ষর নেই, তাই দুই সম্ভাবনার বড়টি।

উত্তর: L[7][6] = 4. কোণ থেকে পেছনে হাঁটলে (মিললে কোণাকুণি, না মিললে বড় দিকে, সমান হলে ওপরে) পাওয়া যায় BCBA. অন্য LCS-ও আছে (যেমন BDAB); “একটি LCS” চাইলে যেকোনো একটি চলে।

Complexity: (n + 1)(m + 1) ঘর, প্রতিটি Θ(1): Θ(nm) সময়, Θ(nm) জায়গা; শুধু দৈর্ঘ্য চাইলে দুই সারি — O(min(n, m)).

নম্বর কোথায়: state-এর অর্থ, base case, দুই case-এর যুক্তি, সম্পূর্ণ টেবিল, পুনর্গঠনের নিয়ম আর উত্তর। পর্ব ৫৪

State: K[i][c] = প্রথম i টি জিনিস থেকে, মোট ওজন ≤ c রেখে, সর্বোচ্চ মূল্য।

উত্তর: K[4][7] = 9: জিনিস ২ আর ৩ (ওজন 3 + 4 = 7, মূল্য 4 + 5 = 9). পুনর্গঠন: K[4][7] = K[3][7] → জিনিস ৪ নেই; K[3][7] ≠ K[2][7] → জিনিস ৩ আছে, c = 3; K[2][3] ≠ K[1][3] → জিনিস ২ আছে, c = 0.

Greedy ব্যর্থ: অনুপাত 1, 1.33, 1.25, 1.4. greedy আগে নেয় (5, 7), বাকি জায়গা 2-এ শুধু (1, 1) — মোট 8 < 9. ভগ্নাংশ নেওয়া গেলে (fractional knapsack) অনুপাত-greedy সেরা, কিন্তু 0/1-এ নয়।

Complexity: Θ(nW) সময়, Θ(nW) জায়গা (এক সারিতে Θ(W), তখন c-কে উল্টো দিকে চালাতে হয়)। এটি pseudo-polynomial — W-এর মানে polynomial, W-এর বিট-সংখ্যায় নয়।

নম্বর কোথায়: state, recurrence-এর দুই শাখা ও শর্ত w_i ≤ c, টেবিল, পুনর্গঠন, আর greedy-র পাল্টা-উদাহরণ। পর্ব ৫৩

State: m[i][j] = A_i…A_j গুণ করার সবচেয়ে কম scalar গুণ; A_i-এর মাত্রা p_i−1 × p_i.

ভরার ক্রম: দৈর্ঘ্য অনুযায়ী (কর্ণ ধরে) — ছোট chain আগে।

• দৈর্ঘ্য ২: m[1][2] = 10·30·5 = 1500; m[2][3] = 30·5·60 = 9000; m[3][4] = 5·60·10 = 3000.
• m[1][3]: k = 1 → 0 + 9000 + 10·30·60 = 27000; k = 2 → 1500 + 0 + 10·5·60 = 4500. সেরা 4500 (k = 2).
• m[2][4]: k = 2 → 0 + 3000 + 30·5·10 = 4500; k = 3 → 9000 + 0 + 30·60·10 = 27000. সেরা 4500 (k = 2).
• m[1][4]: k = 1 → 0 + 4500 + 10·30·10 = 7500; k = 2 → 1500 + 3000 + 10·5·10 = 5000; k = 3 → 4500 + 0 + 10·60·10 = 10500. সেরা 5000 (k = 2).

উত্তর: 5000 গুণ, বন্ধনী ((A₁A₂)(A₃A₄)). পাঁচটি সম্ভাব্য বন্ধনীর মধ্যে সবচেয়ে খারাপটি (A₁(A₂A₃))A₄: 9000 + 18000 + 6000 = 33000 — সেরার ছয় গুণেরও বেশি।

Complexity: Θ(n²) টি ঘর, প্রতিটিতে O(n) টি k: Θ(n³) সময়, Θ(n²) জায়গা।

নম্বর কোথায়: মাত্রার নির্দেশ p_i−1 × p_i, প্রতিটি k-এর হিসাব আলাদা করে, s টেবিল (সেরা k) থেকে বন্ধনী। পর্ব ৫৪

সংজ্ঞা: prefix function π[q] = P[0..q]-এর সবচেয়ে লম্বা এমন proper prefix-এর দৈর্ঘ্য, যা ওই অংশের suffix-ও (border). মিল ভাঙলে KMP pattern-কে কতটা সরাবে, তা এটিই বলে — text-এর pointer কখনো পেছনে যায় না।

Pseudocode: PREFIX-FUNCTION(P[0..m-1])
pi[0] = 0;  k = 0
for q = 1 to m-1:
    while k > 0 and P[k] != P[q]:
        k = pi[k-1]              // fall back to a shorter border
    if P[k] == P[q]: k = k + 1
    pi[q] = k

"ababaca": π = 0, 0, 1, 2, 3, 0, 1. যেমন q = 4: "ababa"-র border "aba", দৈর্ঘ্য 3; q = 5-এ 'c' কোনো border বাড়াতে পারে না, k পড়ে যায় 3 → 1 → 0.

O(m) প্রমাণ (aggregate / potential): k-কে একটি সঞ্চয় হিসেবে ভাবুন। for-লুপের প্রতিটি ঘোরায় k সর্বোচ্চ 1 বাড়ে, তাই মোট বৃদ্ধি ≤ m − 1. while-লুপের প্রতিটি ধাপে k কঠোরভাবে কমে (π[k−1] < k), আর k কখনো ঋণাত্মক হয় না। তাই while-এর মোট ধাপ ≤ মোট বৃদ্ধি ≤ m − 1. মোট কাজ O(m). ∎ একই যুক্তিতে n দৈর্ঘ্যের text-এ খোঁজা O(n), সব মিলিয়ে O(n + m) — naive-এর O(nm)-এর বদলে।

নম্বর কোথায়: সংজ্ঞায় “proper” শব্দটি, প্রতিটি π মান, আর “k মোট যত বাড়ে তার বেশি কমতে পারে না” যুক্তি। পর্ব ৫৮

Pseudocode: PLACE(r)                 // queens already in rows 0..r-1
if r == n: record solution; return
for c = 0 to n-1:
    if not col[c] and not d1[r+c] and not d2[r-c+n-1]:
        put queen at (r, c); mark col[c], d1[r+c], d2[r-c+n-1]
        PLACE(r + 1)
        remove queen; unmark the three      // undo = backtrack

ব্যাখ্যা: প্রতি সারিতে একটি রানি — তাই সারির সংঘর্ষ আপনা থেকেই নেই। কলাম আর দুই কর্ণের চিহ্ন দিয়ে প্রতিটি পরীক্ষা O(1). সংঘর্ষ হলে সেই শাখার পুরো subtree না দেখেই ফেরা — এটিই pruning.

Complexity: সরল সীমা O(n!) (সারি r-এ বড়জোর n − r টি কলাম খোলা), আর কর্ণের pruning বাস্তবে এর চেয়ে অনেক কম। n = 8-এ সমাধান ৯২টি। জায়গা Θ(n).

নম্বর কোথায়: base case, “চেষ্টা → recurse → undo” তিন অংশ, কর্ণের সূচক r + c আর r − c, আর pruning-এর ব্যাখ্যা। পর্ব ৫৬

সমস্যা: 0 থেকে শুরু করা একটি binary counter-এ n বার increment; খরচ = কয়টি বিট উল্টায়। একটি increment-এর worst case Θ(k) (যেমন 0111…1 → 1000…0). তাহলে n বারে কি O(nk)? না — O(n).

(১) Aggregate: বিট 0 প্রতিবার উল্টায়, বিট 1 প্রতি দুবারে একবার, বিট i প্রতি 2ⁱ বারে একবার। মোট ≤ Σ n/2ⁱ < 2n. প্রতি increment amortized < 2.

(২) Accounting: একটি বিট 0 → 1 করতে ২ টাকা নিন: ১ টাকা এখনকার উল্টানোয়, ১ টাকা সেই বিটের গায়ে জমা। পরে 1 → 0 উল্টানোর খরচ সেই জমা টাকাই দেয়। প্রতি increment-এ ঠিক একটি বিট 0 → 1 হয় (counter উপচে না পড়লে), তাই amortized খরচ 2.

(৩) Potential: Φ = counter-এ 1-এর সংখ্যা (≥ 0, শুরুতে 0). একটি increment t টি 1-কে 0 করে আর একটি 0-কে 1: আসল খরচ t + 1, ΔΦ = 1 − t. amortized = (t + 1) + (1 − t) = 2. ∎

যাচাই: 0 থেকে 16 বার increment-এ মোট ৩১টি বিট উল্টায় — 2·16 = 32-এর নিচে।

নম্বর কোথায়: তিন পদ্ধতির নাম ও প্রতিটির নিজস্ব হিসাব, potential-এ Φ ≥ 0 আর Φ₀ = 0 শর্ত। পর্ব ৬০

• P: যে decision problem polynomial সময়ে সমাধান করা যায়।
• NP: যেটির “হ্যাঁ” উত্তরের একটি certificate polynomial সময়ে যাচাই করা যায় (সমতুল্যভাবে, nondeterministic polynomial time). NP মানে “non-polynomial” নয়। P ⊆ NP.
• NP-hard: NP-র প্রতিটি সমস্যা polynomial সময়ে এতে reduce হয় — অন্তত NP-র কঠিনতম সমস্যার মতো কঠিন; নিজে NP-তে না-ও থাকতে পারে।
• NP-complete: NP-তে আছে এবং NP-hard.

প্রমাণের ধাপ: (১) নতুন সমস্যা B NP-তে আছে — certificate আর তার polynomial যাচাইকারী দেখান। (২) একটি জানা NP-complete সমস্যা A বাছুন (যেমন 3-SAT). (৩) A-র যেকোনো instance x থেকে B-র instance f(x) বানানোর polynomial-সময়ের রূপান্তর দিন। (৪) x “হ্যাঁ” ⇒ f(x) “হ্যাঁ”. (৫) f(x) “হ্যাঁ” ⇒ x “হ্যাঁ”. তাহলে A ≤_p B, আর B NP-complete.

নম্বর কোথায়: reduction-এর দিক — জানা কঠিন থেকে নতুনে; উল্টো দিকে (B → A) দেখালে শুধু প্রমাণ হয় B সহজ-বা-সমান, কঠিন নয়। পর্ব ৬৪

সমস্যা: Independent Set — গ্রাফ G আর সংখ্যা k দেওয়া; এমন k টি vertex আছে কি, যাদের কোনো দুটি edge দিয়ে যুক্ত নয়?

NP-তে: certificate = k টি vertex-এর তালিকা; সব জোড়া দেখে edge নেই কি না যাচাই O(k²) বা O(V + E).

রূপান্তর: 3-CNF সূত্র φ-তে m টি clause. প্রতিটি clause-এর তিনটি literal-এর জন্য তিনটি vertex, পরস্পর যুক্ত (clause-ত্রিভুজ)। তারপর ভিন্ন clause-এর যেকোনো x আর ¬x vertex-এর মধ্যে একটি “বিরোধের” edge. k = m. গ্রাফে 3m টি vertex, edge O(m²) — polynomial সময়।

(⇒): φ সত্য করে এমন একটি মান-বণ্টন নিন। প্রতিটি clause থেকে একটি সত্য literal-এর vertex বাছুন — m টি। দুটি একই ত্রিভুজে নয় (প্রতি clause-এ একটি), আর বিরোধের edge শুধু x আর ¬x-এর মধ্যে, যারা একসাথে সত্য হতে পারে না। তাই এটি m আকারের independent set.

(⇐): m আকারের একটি independent set S নিন। প্রতিটি ত্রিভুজ থেকে সর্বোচ্চ একটি, আর ত্রিভুজ m টি — তাই প্রতিটি থেকে ঠিক একটি। S-এর literal-গুলো সত্য ধরুন; x আর ¬x দুটোই S-এ থাকতে পারে না (বিরোধের edge), তাই বণ্টনটি সংগত; বাকি চলক যা খুশি। প্রতিটি clause-এ একটি সত্য literal, তাই φ সত্য। ∎

উদাহরণ: φ = (x₁ ∨ x₂ ∨ x₃) ∧ (¬x₁ ∨ ¬x₂ ∨ x₃) ∧ (x₁ ∨ ¬x₂ ∨ ¬x₃): ৯টি vertex, ৯টি ত্রিভুজ-edge, ৬টি বিরোধের edge, k = 3. x₁ = 1, x₂ = 0, x₃ = 0 থেকে S = {C1.x₁, C2.¬x₂, C3.x₁}.

নম্বর কোথায়: NP-তে থাকা, রূপান্তরের দুই রকম edge আর k = m, polynomial আকার, আর দুই দিকের প্রমাণ — বিশেষ করে (⇐)-তে “প্রতি ত্রিভুজে ঠিক একটি”. পর্ব ৬৪

সমস্যা: vertex cover = এমন vertex-সেট, যাতে প্রতিটি edge-এর অন্তত এক প্রান্ত আছে; সবচেয়ে ছোটটি খোঁজা NP-hard.

Pseudocode: APPROX-VERTEX-COVER(G)
C = empty set
for each edge (u, v) in any order:
    if u not in C and v not in C:    // edge still uncovered
        C = C + {u, v}
return C

প্রমাণ: যে edge-গুলোর জন্য দুই প্রান্ত যোগ হলো, তাদের সেট M. এদের কোনো দুটি একই vertex ছোঁয় না — M একটি maximal matching, আর |C| = 2|M|. বৈধতা: প্রতিটি edge হয় M-এ, নয়তো দেখার সময় এক প্রান্ত C-তে ছিল — তাই সব edge ঢাকা। সীমা: যেকোনো cover-কে M-এর প্রতিটি edge ঢাকতে প্রতিটি থেকে অন্তত একটি প্রান্ত নিতে হয়, আর M-এর edge-গুলোর প্রান্ত আলাদা — তাই OPT ≥ |M|. সুতরাং |C| = 2|M| ≤ 2·OPT. ∎

Complexity: O(V + E). সীমাটি আঁটসাঁট: ৬টি vertex-এর একটি cycle-এ অ্যালগরিদম ৬টি নিতে পারে, অথচ OPT = 3 — নিচের প্রোগ্রাম দেখুন।

নম্বর কোথায়: বৈধতা আর OPT ≥ |M| — দুটি আলাদা দাবি; “approximation ratio = সব ইনপুটে ALG/OPT-এর সর্বোচ্চ” সংজ্ঞাটি। পর্ব ৬৬

নম্বর কোথায়: কোনটিতে সময় এলোমেলো আর কোনটিতে উত্তর — এই এক লাইন, আর প্রতিটির একটি উদাহরণ। পর্ব ৬১

অ্যালগরিদম ভাষা-নিরপেক্ষ ধাপের পরিকল্পনা, যা সব ইনপুটে থামে আর সঠিক উত্তর দেয়; প্রোগ্রাম হলো কোনো নির্দিষ্ট ভাষায় তার রূপ — আর একটি প্রোগ্রাম চিরকাল চলতেও পারে (যেমন সার্ভার)। পর্ব ০২

না। Big-O একটি ফাংশনের ওপরের সীমা; best, worst বা average — যেকোনো case-এর ফাংশনকে O দিয়ে বলা যায়। “insertion sort-এর best case O(n)” একটি সঠিক বাক্য। পর্ব ০৪

না। Big-O ধ্রুবক আর ছোট n লুকায় — 1000n ধাপের অ্যালগরিদম n < 1000-এ n² ধাপের চেয়ে ধীর। এজন্যই বাস্তবের sort ছোট অংশে insertion sort ব্যবহার করে। পর্ব ০৪

log_a n = log_b n / log_b a — base বদলালে শুধু একটি ধ্রুবক গুণ বদলায়, যা O, Ω, Θ উপেক্ষা করে। তবে সূচকে (যেমন n^{log₂ 3}) base জরুরি। পর্ব ০৬

ফাংশন নিজেকে ডাকতেই থাকে; প্রতিটি ডাক call stack-এ একটি frame যোগ করে, আর stack-এর সীমা ফুরোলে প্রোগ্রাম stack overflow-এ ভেঙে পড়ে (Python-এ RecursionError). পর্ব ০৭

যখন recurrence aT(n/b) + f(n) ছাঁচে নয় — যেমন T(n − 1) + n বা T(n/3) + T(2n/3) + n — অথবা f আর n^{log_b a}-এর ফারাক polynomial নয় (যেমন 2T(n/2) + n/log n). তখন recursion tree বা substitution ধরুন। পর্ব ০৯

Stack LIFO — শেষে ঢোকা আগে বের হয়, যেমন থালার স্তূপ, undo বা function call; queue FIFO — আগে ঢোকা আগে বের হয়, যেমন টিকিটের লাইন, printer-এর কাজ বা BFS. দুটিতেই মূল কাজগুলো O(1). পর্ব ১৩ · পর্ব ১৪

উপাদানগুলো মেমরিতে পাশাপাশি আর সমান আকারের, তাই ঠিকানা = শুরুর ঠিকানা + i × আকার — একটি গুণ আর একটি যোগ, i যত বড়ই হোক। পর্ব ১০

এটি amortized O(1): ধারণক্ষমতা দ্বিগুণ হয় বলে n টি push-এ মোট কপি 2n-এর কম, তাই গড়ে প্রতি push ধ্রুবক; একটি একক push-এর worst case অবশ্য Θ(n). পর্ব ১০

মাঝের node-এ পৌঁছাতেই হাঁটতে হয় Θ(n) — random access নেই; মোট হাঁটা n/2 + n/4 + … = Θ(n), তুলনা কম হলেও সময় linear search-এর মতোই। দ্রুত খোঁজার জন্য BST বা skip list লাগে। পর্ব ১২

Θ(n) প্রস্তুতিতে যেকোনো পরিসরের যোগফল O(1)-এ: sum(l..r) = P[r + 1] − P[l]. কিন্তু অ্যারে বদলালে পুরো P আবার বানাতে হয় — তখন Fenwick বা segment tree. পর্ব ১৭

পাশাপাশি অংশ (subarray/substring)-এর প্রশ্নে, যখন জানালা বড় করলে শর্তটি এক দিকেই বদলায় — যেমন অ-ঋণাত্মক সংখ্যায় “যোগফল ≤ K”. ঋণাত্মক সংখ্যা থাকলে এই একমুখিতা ভাঙে, তখন prefix sum + hash map. পর্ব ১৬

সাজানো ডেটা (আরও সাধারণভাবে একমুখী — monotonic — শর্ত) আর random access. উত্তরের ওপর binary search-এ “x-এ সম্ভব হলে x-এর চেয়ে বড়তেও সম্ভব” — এই একমুখিতাই শর্ত। পর্ব ১৮ · পর্ব ১৯

in-place, আর partition অ্যারের ওপর দিয়ে পরপর হাঁটে বলে cache খুব ভালো কাজে লাগে; ভেতরের লুপ ছোট, ধ্রুবক কম; এলোমেলো pivot-এ worst case প্রায় অসম্ভব। লাইব্রেরি (যেমন introsort) গভীরতা বেশি হলে heapsort-এ চলে গিয়ে O(n log n) নিশ্চিত করে। পর্ব ২২

সমান কী-এর উপাদানের আগের ক্রম রাখে। দরকার একাধিক কী-তে সাজাতে — যেমন আগে নাম ধরে, তারপর stable sort-এ বিভাগ ধরে সাজালে প্রতি বিভাগে নাম ক্রমে থাকে — আর LSD radix sort-এ। পর্ব ২৫

stability, linked list বা ডিস্কের বিশাল ফাইল (external sort) আর নিশ্চিত Θ(n log n) চাইলে merge sort; মেমরি কম আর অ্যারেতে গড়ে দ্রুততম চাইলে quick sort. পর্ব ২১

না, কারণ সীমাটি শুধু তুলনা-ভিত্তিক সর্টের জন্য। counting sort কী-কে index হিসেবে ব্যবহার করে — পূর্ণসংখ্যা আর ছোট পরিসর k ধরে নেয় — তাই Θ(n + k). পর্ব ২৪

heap property শুধু মা-বাবা আর সন্তানের ক্রম বলে, বাঁ আর ডানের মধ্যে কোনো ক্রম নেই — তাই কোন দিকে যেতে হবে বোঝা যায় না, সব দেখতে হয়। heap শুধু min বা max দ্রুত দেয়। পর্ব ২৩

সব key একই bucket-এ গেলে একটি তালিকায় n টি key — দুর্বল hash function বা ইচ্ছা করে সংঘর্ষ ঘটানো ইনপুটে এমন হয়। ভালো hash আর সীমিত load factor-এ প্রত্যাশিত সময় O(1), কিন্তু সেটি নিশ্চয়তা নয়। পর্ব ৩২

সব key ছোট থেকে বড় ক্রমে — বাঁ subtree, মূল, ডান subtree; সময় Θ(n). এটি দিয়েই কোনো binary tree BST কি না যাচাই করা যায়। পর্ব ২৭

AVL বেশি কড়া ভারসাম্য রাখে (উচ্চতা ≈ 1.44 log n বনাম red-black-এর ≤ 2 log(n + 1)), তাই খোঁজা একটু দ্রুত; red-black insert-এ সর্বোচ্চ ২টি আর delete-এ সর্বোচ্চ ৩টি rotation করে, তাই ঘন ঘন পরিবর্তনে সুবিধা — অনেক লাইব্রেরির ordered map এজন্য red-black ব্যবহার করে। পর্ব ২৯

prefix-এর প্রশ্নে — “এই prefix দিয়ে কয়টি শব্দ শুরু?”, autocomplete, অভিধান ক্রমে তালিকা; খরচ শব্দের দৈর্ঘ্য L-এ O(L), n-এ নির্ভর করে না। hash table prefix খুঁজতে পারে না। পর্ব ৩১

find-এর সময় পথের প্রতিটি node-কে সরাসরি মূলের সাথে জুড়ে দেয়, তাই পরের find প্রায় এক ধাপে হয়; union by rank-এর সাথে প্রতি কাজ amortized O(α(n)). পর্ব ৩৩

Fenwick ছোট কোড আর n ঘরের জায়গায় prefix-ভিত্তিক কাজ (যোগফল, উল্টানো যায় এমন অপারেশন) করে; segment tree যেকোনো associative কাজ (min, max, gcd) আর lazy propagation-এ range update পারে — দুটিতেই query ও update O(log n). পর্ব ৩৬

BFS queue দিয়ে স্তরে স্তরে ছড়ায় আর unweighted গ্রাফে সবচেয়ে ছোট পথ দেয়; DFS stack বা recursion দিয়ে এক পথে যতদূর সম্ভব যায়, আর cycle, topological order, SCC, bridge খুঁজতে কাজে লাগে। দুটিই Θ(V + E). পর্ব ৪০ · পর্ব ৪১

matrix-এ জায়গা Θ(V²), “u-v edge আছে?” O(1) — ঘন গ্রাফ বা Floyd-Warshall-এ; list-এ Θ(V + E), প্রতিবেশী ঘোরা দ্রুত — বেশিরভাগ বাস্তব গ্রাফ পাতলা, তাই সাধারণত list. পর্ব ৩৯

মিল: দুটিই greedy, priority queue থেকে প্রতিবার সবচেয়ে ছোট key-এর vertex নিয়ে একটি tree বড় করে, complexity একই — O((V + E) log V). অমিল: Dijkstra-র key উৎস থেকে মোট দূরত্ব d[u] + w, Prim-এর key শুধু tree-তে জোড়ার edge-এর weight w; Dijkstra দেয় shortest-path tree, Prim দেয় MST — আর Prim ঋণাত্মক weight-এও ঠিক থাকে, Dijkstra থাকে না। পর্ব ৪৩ · পর্ব ৪৫

Dijkstra ধরে নেয় একটি vertex settle হলে তার দূরত্ব আর কমবে না, কারণ অ-ঋণাত্মক weight-এ পথ বাড়ালে দৈর্ঘ্য কমে না; ঋণাত্মক edge থাকলে পরে আসা পথ ছোট হতে পারে — ঙ-০৩-এর S, A, B, C উদাহরণে A = 1 না হয়ে 2 আসে, negative cycle ছাড়াই। পর্ব ৪৩

এক উৎস থেকে, ঋণাত্মক edge থাকলে বা negative cycle খুঁজতে Bellman-Ford — Θ(VE); সব জোড়ার দূরত্ব, ছোট বা ঘন গ্রাফে Floyd-Warshall — Θ(V³) সময়, Θ(V²) জায়গা। পর্ব ৪৪

যেখানে কাজের আগে-পরে নির্ভরতা আছে — কোর্সের পূর্বশর্ত, build system-এ কোন ফাইল আগে compile, package install-এর ক্রম, spreadsheet-এর সূত্রের হিসাব। cycle থাকলে কোনো বৈধ ক্রম নেই। পর্ব ৪২

greedy প্রতি ধাপে একটি স্থানীয় সেরা পছন্দ করে আর কখনো ফেরে না — প্রমাণ (exchange) লাগে; DP সব পছন্দের ছোট সমস্যা সমাধান করে মনে রাখে আর তুলনা করে বাছে — ধীর হতে পারে কিন্তু greedy-choice property ছাড়াই ঠিক। coin {1, 3, 4}-এ 6 টাকা: greedy 4 + 1 + 1 (৩টি), DP 3 + 3 (২টি)। পর্ব ৫০ · পর্ব ৫২

memoization ওপর থেকে নিচে — রিকার্সিভ ফাংশন, প্রথমবার হিসাব করে মনে রাখে, শুধু দরকারি state ছোঁয়; tabulation নিচ থেকে ওপরে — লুপে ক্রম মেনে পুরো টেবিল ভরে, recursion-এর stack লাগে না আর জায়গা বাঁচানো সহজ। পর্ব ৫২

ইনপুটের আকার W-এর বিট-সংখ্যা log W, মান W নয়; W = 2^b হলে nW = n·2^b — ইনপুট-আকারে সূচকীয়। এটিই pseudo-polynomial; W ছোট হলে DP কাজের, বড় হলে নয়। পর্ব ৫৩

brute force সব সম্পূর্ণ সমাধান তৈরি করে তারপর যাচাই করে; backtracking আংশিক সমাধানেই শর্ত ভাঙলে সেই শাখা ছেঁটে ফেলে (pruning) — worst case একই থাকতে পারে, কিন্তু বাস্তবে অনেক কম শাখা দেখে। পর্ব ৫৬

naive মিল ভাঙলে text-এ পেছনে ফিরে আবার শুরু করে — O(nm); KMP prefix function দিয়ে জানে ইতিমধ্যে মেলা অংশের কতটুকু কাজে লাগবে, তাই text-এর pointer কখনো পেছনে যায় না — O(n + m). পর্ব ৫৮

amortized হলো যেকোনো কাজের ক্রমে worst case-এর গড় — কোনো সম্ভাবনা বা ইনপুট-বণ্টন লাগে না, নিশ্চয়তা; average case নির্ভর করে ইনপুটের সম্ভাব্যতা-বণ্টনের অনুমানের ওপর। পর্ব ৬০

না — nondeterministic polynomial: যে সমস্যার “হ্যাঁ” উত্তর একটি প্রমাণ (certificate) দেখে polynomial সময়ে যাচাই করা যায়। P-র সব সমস্যাও NP-তে আছে। পর্ব ৬৪

NP-complete = NP-তে আছে এবং NP-hard; NP-hard সমস্যা NP-র বাইরেও হতে পারে — যেমন halting problem, বা TSP-র optimization রূপ (“সবচেয়ে ছোট tour কত?”), যার উত্তর যাচাই করা সহজ নয়। পর্ব ৬৪

জানা কঠিন সমস্যা A থেকে B-তে: A ≤_p B — অর্থাৎ B সমাধান করতে পারলে A-ও পারা যেত। উল্টো দিকে করলে শুধু দেখায় B, A-র চেয়ে কঠিন নয়। পর্ব ৬৪

প্রতিটি ইনপুটে অ্যালগরিদমের সমাধানের খরচ সেরা সমাধানের সর্বোচ্চ দ্বিগুণ (minimization-এ) — গড়ে নয়, সবসময়; আর সেরা সমাধান না জেনেও এটি প্রমাণ করা হয় OPT-এর একটি নিম্নসীমা দিয়ে। পর্ব ৬৬

ইনপুট ছোট হলে exact (backtracking, bitmask DP, branch and bound); বিশেষ গঠন থাকলে (tree, bipartite, ছোট প্যারামিটার) সেটির দ্রুত অ্যালগরিদম; নইলে প্রমাণিত approximation বা heuristic — আর সবসময় ইনপুটের সীমা দেখে সিদ্ধান্ত। পর্ব ৬৫