DSA-র গণিত — log, যোগফল আর ধারা

১ · কেন গণিত — অ্যালগরিদমের হিসাবের ভাষা

পর্ব ০৪-এ আপনি দেখেছেন, একটি অ্যালগরিদম কত দ্রুত তা আমরা মাপি “ইনপুট n বাড়লে ধাপের সংখ্যা কীভাবে বাড়ে” দিয়ে, আর লিখি Big-O বা Θ দিয়ে। পর্ব ০৫-এ দেখেছেন best, worst আর average case. কিন্তু একটা প্রশ্ন বাকি থেকে গেছে — ধাপের সংখ্যাটা আসলে গুনব কীভাবে?

উত্তরটা মজার। কোনো প্রোগ্রামের সময় প্রায় পুরোটাই খরচ হয় লুপে আর রিকার্শনে। আর লুপ গুনতে গেলে যে প্রশ্নগুলো বারবার আসে, সেগুলো আসলে স্কুলের গণিতের পুরোনো বন্ধু:

ভয় পাওয়ার কিছু নেই। এই পর্বে ক্যালকুলাস প্রায় লাগবে না, লাগবে স্কুলের বীজগণিত আর একটু ধৈর্য। প্রতিটি সূত্র আমরা প্রথমে ছোট উদাহরণে হাতে মিলিয়ে দেখব, তারপর প্রমাণ করব, তারপর কম্পিউটারে বড় n-এ যাচাই করব। যাঁরা আগে থেকেই জানেন, তাঁদের জন্য প্রতিটি অংশে একটু গভীর কথাও থাকবে।

২ · Logarithm — কতবার অর্ধেক করা যায়

প্রথমে সংজ্ঞা। Logarithm হলো সূচক বা ঘাতের উল্টো প্রশ্ন:

এভাবে পড়লে log একটু শুকনো লাগে। কম্পিউটার বিজ্ঞানে log₂ n-কে পড়ুন অনেক সহজ একটি প্রশ্ন হিসেবে:

অর্ধেক করার কাজটি একটি ছোট while লুপ। Pseudocode (চলক পূর্ণসংখ্যা, ভাগ মানে নিচের দিকে গোল করা ভাগ):

HALVINGS(n)            // n ≥ 1
    steps ← 0
    while n > 1
        n ← ⌊n / 2⌋
        steps ← steps + 1
    return steps           // = ⌊log₂ n⌋

এবার n = ১০০ দিয়ে লুপটি ধাপে ধাপে চালিয়ে দেখুন। “পরে” চাপুন আর ডান দিকে n আর steps-এর মান খেয়াল করুন:

1int n = 100, steps = 0;2while (n > 1) {3    n = n / 2;      // floor4    steps++;5}6printf("steps = %d\n", steps);

Binary search-এর গভীরতা: ⌈log₂(n+1)⌉

পর্ব ১৮-এ আপনি binary search বিস্তারিত শিখবেন। এখানে শুধু হিসাবটা দেখি। প্রতিটি তুলনার পর খোঁজার জায়গা অন্তত অর্ধেক হয়ে যায়। worst case-এ সর্বোচ্চ যতগুলো তুলনা লাগে, তা হলো ⌊log₂ n⌋ + 1 = ⌈log₂(n+1)⌉. কেন +১? কারণ শেষে একটি উপাদান বাকি থাকলেও সেটিকে একবার দেখতে হয়। k টি তুলনায় সর্বোচ্চ 2^k − 1 টি উপাদান সামলানো যায় (১ + ২ + ৪ + … — এই ধারা অংশ ৬-এ প্রমাণ করব), তাই 2^k − 1 ≥ n হওয়া চাই, অর্থাৎ k ≥ log₂(n+1).

শেষ সারিটি ভালো করে দেখুন। বাংলাদেশের মোট জনসংখ্যার কয়েক গুণ বড় একটি সাজানো তালিকাতেও মাত্র ৩০ বার দেখলেই যেকোনো নাম পাওয়া যায় বা নিশ্চিত হওয়া যায় যে নেই। log-এর এই “ধীরে বাড়া” স্বভাবই অসংখ্য দ্রুত ডেটা স্ট্রাকচারের মূল রহস্য। আরেকটি কাজের তথ্য: একটি ধনাত্মক পূর্ণসংখ্যা n লিখতে ঠিক ⌊log₂ n⌋ + 1 টি bit লাগে। যেমন ১০০ = 1100100 — সাতটি bit.

নিচের ছোট টুলটি চালান। শুরুতে এটি কয়েকটি n-এর জন্য হিসাব ছাপবে আর ১০০-কে অর্ধেক করার প্রতিটি ধাপ বার হিসেবে আঁকবে। তারপর ঘরে নিজের পছন্দের সংখ্যা লিখে “অর্ধেক করুন” চাপুন — বারগুলো কত দ্রুত ছোট হয়ে যায়, দেখুন:

// n-কে বারবার অর্ধেক (নিচের দিকে গোল) করলে কত ধাপে 1 হয়?
function halvings(n) {
  const seq = [n];
  while (n > 1) { n = Math.floor(n / 2); seq.push(n); }
  return seq;
}
function draw() {
  const n0 = Math.max(1, Math.floor(Number(document.getElementById('num').value) || 1));
  const seq = halvings(n0);
  document.getElementById('viz').innerHTML = seq.map((v, i) =>
    `<div class="row"><span class="lab">step ${i}: ${v}</span>` +
    `<span class="bar" style="width:${Math.max(0.5, 70 * v / n0)}%"></span></div>`).join('');
  document.getElementById('sumry').textContent =
    `${seq.length - 1} halvings, floor(log2 n) = ${Math.floor(Math.log2(n0))}`;
}
document.getElementById('go').onclick = draw;
draw();
for (const n of [1, 2, 7, 8, 100, 1000000, 1000000000])
  console.log(`n=${n}: halvings=${halvings(n).length - 1}, floor(log2 n)=` +
    `${Math.floor(Math.log2(n))}, ceil(log2(n+1))=${Math.ceil(Math.log2(n + 1))}`);

৩ · Log-এর নিয়ম, ভিত্তি বদল আর log n!

log নিয়ে হিসাব করতে কয়েকটি নিয়মই যথেষ্ট। সবগুলো এসেছে একটি সরল সত্য থেকে: ঘাত গুণ করলে সূচক যোগ হয় (2^a · 2^b = 2^a+b). log সূচক নিয়ে কাজ করে, তাই গুণ log-এ গিয়ে যোগ হয়ে যায়।

ভিত্তি বদল: কেন O(log n)-এ ভিত্তি লেখা হয় না

শেষ সারির নিয়মটির নাম change of base. এর মানে, log₂ n আর log₁₀ n-এর মধ্যে পার্থক্য শুধু একটি ধ্রুবক গুণক (প্রায় ৩.৩২)। Big-O ধ্রুবক গুণক উপেক্ষা করে, তাই O(log₂ n) = O(log₁₀ n) = O(ln n) — সবাই শুধু O(log n). একটি B-tree (পর্ব ৩০) যদি প্রতিটি node-এ ১০০ ভাগে ভাগ করে, তার উচ্চতা log₁₀₀ n — তবু সেটিও Θ(log n). ব্যবহারিক পার্থক্য অবশ্য আছে: ১০০ কোটিতে log₂ প্রায় ৩০, আর log₁₀₀ মাত্র ৪.৫. ডিস্কে প্রতিটি ধাপ দামি হলে এই ধ্রুবকই আসল খেলা।

log n! = Θ(n log n) — দুই লাইনের প্রমাণ

Factorial n! = 1 · 2 · 3 · … · n. প্রথম নিয়ম অনুযায়ী log n! = log 1 + log 2 + … + log n. এটি কত বড়? দুই দিক থেকে চেপে ধরি:

• ঊর্ধ্বসীমা: প্রতিটি গুণক ≤ n, তাই n! ≤ nⁿ, অর্থাৎ log n! ≤ n log n.
• নিম্নসীমা: শেষের অর্ধেক গুণক (n/2 থেকে n) প্রতিটি ≥ n/2, আর এমন গুণক অন্তত n/2 টি। বাকিগুলো ≥ 1. তাই n! ≥ (n/2)^n/2, অর্থাৎ log n! ≥ (n/2) · log(n/2) = (n/2)(log n − 1), যা n ≥ 4 হলে ≥ (n/4) log n.

দুই সীমাই n log n-এর ধ্রুবক গুণ, তাই log n! = Θ(n log n). আরও সূক্ষ্ম হিসাব দেয় Stirling's approximation:

এর অন্তর্নিহিত ধারণাটা সহজ: n! আসলে প্রায় n টি গুণকের গুণফল, যাদের “গড় আকার” প্রায় n/e. তাই n! মোটামুটি (n/e)ⁿ. পর্ব ২৪-এ এই সূত্রটিই প্রমাণ করবে যে শুধু তুলনা করে সাজায় এমন যেকোনো সর্টের worst case-এ অন্তত log₂ n! ≈ n log₂ n তুলনা লাগবেই — merge sort বা heapsort-এর চেয়ে ভালো (ধ্রুবক বাদে) তুলনা-সর্ট সম্ভব নয়।

৪ · Floor, ceiling, exponential আর modular arithmetic

Floor আর ceiling — গোল করার দুই দিক

অ্যালগরিদমে n টি জিনিস প্রায়ই সমান দুই ভাগে ভাগ হয় না। ৭টি জিনিসের অর্ধেক ৩.৫ — কিন্তু অর্ধেক জিনিস তো হয় না! তখন লাগে floor ⌊x⌋ (নিচের দিকে গোল, ⌊3.5⌋ = 3) আর ceiling ⌈x⌉ (ওপরের দিকে গোল, ⌈3.5⌉ = 4). কয়েকটি কাজের তথ্য:

• ⌊n/2⌋ + ⌈n/2⌉ = n — merge sort যখন ৭টিকে ৩ আর ৪-এ ভাগ করে, কিছুই হারায় না।
• ধনাত্মক পূর্ণসংখ্যা a, b-এর জন্য ⌈a/b⌉ = ⌊(a + b − 1)/b⌋. যেমন ২৩ জন যাত্রী, প্রতি রিকশায় ২ জন — লাগবে ⌈23/2⌉ = (23 + 1)/2 = ১২টি রিকশা। কোডে লিখুন (a + b - 1) / b, float-এর ceil নয়।
• C++-এর / শূন্যের দিকে কাটে: -7 / 2 = −3. Python-এর // সত্যিকারের floor: -7 // 2 = −4. ঋণাত্মক সংখ্যায় দুই ভাষার উত্তর আলাদা!

Exponential — দ্বিগুণের ভয়ংকর গতি

log-এর ঠিক উল্টো হলো 2ⁿ. এর বৃদ্ধি এত দ্রুত যে মানুষের অনুভূতি তাল রাখতে পারে না। দাবার বোর্ডের প্রচলিত লোককথাটি হয়তো শুনেছেন: প্রথম ঘরে ১টি চাল, পরের ঘরে ২টি, তারপর ৪টি — প্রতি ঘরে দ্বিগুণ। ৬৪টি ঘরে মোট 2⁶⁴ − 1 টি চাল, যা পৃথিবীর সব ধানখেতের বহু বছরের ফলনের চেয়েও বেশি। Exponential growth চেনার জন্য কয়েকটি মান মনে রাখুন:

কনটেস্টের একটি চালু নিয়ম: “এক সেকেন্ডে মোটামুটি 10⁸ সরল কাজ।” তাহলে n = ২০ হলে 2ⁿ ≈ ১০ লাখ — নির্ভয়ে সব সম্ভাবনা দেখা যায়; n = ৪০ হলে 2⁴⁰ ≈ 10¹² — কয়েক ঘণ্টা! n মাত্র দ্বিগুণ হলো, কিন্তু সময় বাড়ল প্রায় দশ লাখ গুণ।

Modular arithmetic — ঘড়ির অঙ্ক

দেয়ালঘড়ি ১২টার পর ১৩টা দেখায় না, আবার ১ থেকে শুরু করে। এটাই modular arithmetic: a mod m মানে a-কে m দিয়ে ভাগ করলে যে ভাগশেষ থাকে (০ থেকে m − 1). যেমন 17 mod 5 = 2. এর সবচেয়ে কাজের বৈশিষ্ট্য — যোগ, বিয়োগ আর গুণের প্রতিটি ধাপে mod নিলেও শেষ ফল বদলায় না:

এজন্যই কনটেস্টে প্রায়ই লেখা থাকে “উত্তর 10⁹ + 7 দিয়ে mod করে দিন।” উত্তর হয়তো ১০০০ অঙ্কের সংখ্যা, কিন্তু প্রতিটি ধাপে mod নিলে সব সংখ্যা long long-এ ধরে যায় (দুটি ১০০ কোটির কম সংখ্যার গুণফল ≈ 10¹⁸ < 9.22 × 10¹⁸). দুটি সতর্কতা: ভাগের জন্য এমন সহজ নিয়ম নেই — সেখানে লাগে modular inverse; আর C++-এ -7 % 3 = −1, অথচ Python-এ -7 % 3 = 2. C++-এ নিরাপদ রূপ: ((a % m) + m) % m. GCD, sieve, দ্রুত ঘাত আর modular inverse নিয়ে পূর্ণ আলোচনা পর্ব ৬২-তে।

৫ · সমান্তর ধারা — Gauss-এর জোড়া বানানোর কৌশল

অঙ্কের ইতিহাসে একটি প্রচলিত গল্প আছে। অষ্টাদশ শতকের শেষ দিকে জার্মানির এক স্কুলে শিক্ষক ক্লাসকে ব্যস্ত রাখতে ১ থেকে ১০০ পর্যন্ত সব সংখ্যা যোগ করতে দিলেন। ছোট্ট Carl Friedrich Gauss প্রায় সঙ্গে সঙ্গেই উত্তর লিখে দিলেন — ৫০৫০. গল্পের খুঁটিনাটি (সংখ্যাগুলো ঠিক কী ছিল, Gauss-এর বয়স কত) নিয়ে ইতিহাসবিদদের মধ্যে মতভেদ আছে, কিন্তু কৌশলটি নিখুঁত: সামনের আর পেছনের সংখ্যা জোড়া বাঁধুন।

নিচের ডায়াগ্রামে n = ১০ দিয়ে কৌশলটি দেখুন। প্রতিটি ধাপে একটি জোড়া লাল দাগে চিহ্নিত হবে:

n বিজোড় হলে কী হবে? মাঝের সংখ্যাটির জোড়া থাকে না। তাই প্রমাণটা আরেকটু পরিচ্ছন্নভাবে লিখি: যোগফল S-কে একবার সামনে থেকে, একবার পেছন থেকে লিখে দুটো যোগ করুন।

এখানে n জোড় না বিজোড় তা লাগেনি — প্রতিটি কলামে যোগফল n + 1, আর কলাম n টি। এই closed form দেখে Θ বলা সহজ: n(n+1)/2 = n²/2 + n/2 = Θ(n²).

বর্গের যোগফল আর সাধারণ নিয়ম

তিন স্তরের লুপে প্রায়ই আসে 1² + 2² + … + n². এর সূত্র:

প্রমাণটা induction দিয়ে সহজ (পর্ব ০৩-এর পদ্ধতি): n = 1-এ দুই দিকেই ১; আর n-এর জন্য সত্য ধরে নিলে n(n+1)(2n+1)/6 + (n+1)² সরল করলে ঠিক (n+1)(n+2)(2n+3)/6 আসে — নিজে কাগজে মিলিয়ে দেখুন। সাধারণ নিয়মটি মনে রাখার মতো: Σ i^k = Θ(n^k+1), অর্থাৎ যোগ করলে ঘাত এক বাড়ে। কারণ? n টি পদ, যার অর্ধেক পদই অন্তত (n/2)^k — তাই যোগফল ≥ (n/2)·(n/2)^k; আবার প্রতিটি পদ ≤ n^k, তাই যোগফল ≤ n · n^k.

৬ · গুণোত্তর ধারা — দ্বিগুণের জাদু

গুণোত্তর ধারায় প্রতিটি পদ আগেরটির একটি নির্দিষ্ট গুণ (r). সবচেয়ে গুরুত্বপূর্ণটি r = 2:

প্রমাণ: যোগফল S. দুই দিকে ২ দিয়ে গুণ করলে 2S = 2 + 4 + … + 2^k+1. এবার 2S − S লিখুন — মাঝের সব পদ কেটে যায়, থাকে শুধু 2^k+1 − 1. Binary-তে আরও সুন্দর দেখায়: 1 + 2 + 4 + 8 = 1111₂ = 15, আর তার ঠিক পরের সংখ্যা 10000₂ = 16.

এই শেষ তথ্যটি অনেক অ্যালগরিদমের রহস্য খুলে দেয়। যদি প্রতিটি ধাপে কাজ অর্ধেক হয়ে যায় (n, তারপর n/2, তারপর n/4…), মোট কাজ 2n-এর কম — অর্থাৎ Θ(n), log n গুণ নয়। Quickselect-এর গড় সময় (পর্ব ২২) আর heap তৈরির O(n) হিসাব (পর্ব ২৩) — দুটোই এই ধারার ওপর দাঁড়িয়ে।

Dynamic array কেন দ্বিগুণ হয়

C++-এর vector বা Python-এর list-এ push_back/append করতে থাকলে জায়গা একসময় ফুরিয়ে যায়। তখন dynamic array একটি বড় নতুন জায়গা নেয় আর পুরোনো সব উপাদান সেখানে কপি করে। কপি করা দামি — তাহলে কি প্রতিটি push ধীর? ক্ষমতা (capacity) প্রতিবার দ্বিগুণ করলে কী হয়, ধাপে ধাপে দেখুন:

সাধারণভাবে n টি push-এ শেষ resize-এর সময় কপি হয় 2^k < n টি উপাদান, আর আগের সবগুলো মিলিয়ে 1 + 2 + … + 2^k < 2^k+1 < 2n. নতুন লেখা n টি ধরলে মোট কাজ < 3n. তাই একটি push কখনো কখনো Θ(n) সময় নিলেও গড়ে Θ(1) — একে বলে amortized O(1). বিস্তারিত আসবে পর্ব ১০ আর পর্ব ৬০-এ।

৭ · Harmonic ধারা আর integral দিয়ে যোগফলের সীমা

তৃতীয় গুরুত্বপূর্ণ ধারাটি harmonic series:

এটি এক অদ্ভুত ধারা। পদগুলো ছোট হতে হতে শূন্যের দিকে যায়, তবু যোগফল কোনো সীমায় থামে না — যত খুশি বড় হয়। কিন্তু বাড়ে অসম্ভব ধীরে: H_n ১০ ছাড়াতে প্রায় ১২ হাজার পদ লাগে। কেন Θ(log n), তা দেখার একটি সুন্দর উপায় হলো পদগুলোকে দল বাঁধা — দলের আকার ১, ২, ৪, ৮…:

n পর্যন্ত মোটামুটি log₂ n টি দল হয়। প্রতিটি দলের যোগফল ½ থেকে ১-এর মধ্যে, তাই H_n-ও (½)·log₂ n থেকে log₂ n + 1-এর মধ্যে আটকে থাকে — Θ(log n). দ্বিতীয় অসমতাটিই দেখায় যে ধারাটি অসীমে যায়: যত দল, তত বার অন্তত ½ যোগ হয়।

Integral দিয়ে যোগফল চেপে ধরা

আরও নিখুঁত সীমা পাওয়ার সাধারণ কৌশল হলো যোগফলকে ক্ষেত্রফল হিসেবে দেখা। f যদি কমতে থাকা ফাংশন হয় (যেমন 1/x), তাহলে প্রতিটি পদ f(i) হলো চওড়ায় ১ একটি আয়তক্ষেত্র, যা বক্ররেখার নিচের ক্ষেত্রফলের সাথে তুলনা করা যায়:

বাড়তে থাকা f-এর জন্য দিক উল্টে যায়: ∫₀ⁿ f(x)dx ≤ Σ_i=1ⁿ f(i) ≤ ∫₁ⁿ⁺¹ f(x)dx. যেমন Σ i² প্রায় ∫ x² dx = n³/3 — অংশ ৫-এর সূত্রের প্রধান পদ এটাই। Σ log i (অর্থাৎ log n!) প্রায় ∫ ln x dx = n ln n − n — Stirling-এর প্রধান অংশ। ক্যালকুলাস না জানলেও চলবে; শুধু মনে রাখুন: মসৃণ ফাংশনের যোগফল আর integral একই হারে বাড়ে।

Harmonic ধারা বাস্তবে কোথায় আসে? এমন লুপে, যেখানে ভেতরের লুপ i-এর ধাপে লাফায়: i = 1-এ n বার, i = 2-এ n/2 বার, i = 3-এ n/3 বার… মোট n · H_n = Θ(n log n). Quicksort-এর গড় তুলনা প্রায় 2n ln n (পর্ব ২২), আর “সব রকম কুপন জোগাড় করতে গড়ে কত কেনা লাগে” — সেটিও n · H_n.

সূত্রগুলো কম্পিউটারে যাচাই

সূত্র প্রমাণ করা হলো, এবার বড় n-এ লুপ চালিয়ে মিলিয়ে দেখি। নিচের প্রোগ্রাম চারটি n-এর জন্য Σ i আর Σ i² লুপে যোগ করে সূত্রের সাথে মেলায়, H_n আর ln n পাশাপাশি দেখায়, আর শেষে কয়েকটি k-এর জন্য 2-এর ঘাতের যোগফল যাচাই করে। আপনার ভাষার ট্যাব বেছে নিন — দুটির আউটপুট হুবহু এক:

#include <cmath>
#include <cstdio>
#include <initializer_list>
int main() {
    for (long long n : {10LL, 100LL, 1000LL, 100000LL}) {   // loop sums vs formulas
        long long s1 = 0, s2 = 0;  double h = 0.0;
        for (long long i = 1; i <= n; i++) {
            s1 += i;
            s2 += i * i;
            h += 1.0 / i;
        }
        bool ok = s1 == n * (n + 1) / 2 && s2 == n * (n + 1) * (2 * n + 1) / 6;
        std::printf("n=%lld sum=%lld squares=%lld %s\n", n, s1, s2, ok ? "OK" : "BAD");
        double ln = std::log(double(n));
        std::printf("   H(n)=%.6f ln(n)=%.6f diff=%.6f\n", h, ln, h - ln);
    }
    for (int k : {3, 10, 20, 40}) {           // 1 + 2 + 4 + ... + 2^k
        long long g = 0;  for (int i = 0; i <= k; i++) g += 1LL << i;
        std::printf("k=%d sum=%lld 2^(k+1)-1=%lld\n", k, g, (1LL << (k + 1)) - 1);
    }
}

import math

# 1) loop sums vs closed-form formulas
for n in (10, 100, 1000, 100000):
    s1 = s2 = 0
    h = 0.0
    for i in range(1, n + 1):
        s1 += i
        s2 += i * i
        h += 1.0 / i
    ok = s1 == n * (n + 1) // 2 and s2 == n * (n + 1) * (2 * n + 1) // 6
    print("n=%d sum=%d squares=%d %s" % (n, s1, s2, "OK" if ok else "BAD"))
    ln = math.log(n)
    print("   H(n)=%.6f ln(n)=%.6f diff=%.6f" % (h, ln, h - ln))

# 2) geometric: 1 + 2 + 4 + ... + 2^k == 2^(k+1) - 1
for k in (3, 10, 20, 40):
    g = sum(1 << i for i in range(k + 1))
    print("k=%d sum=%d 2^(k+1)-1=%d" % (k, g, (1 << (k + 1)) - 1))

৮ · গণনার মৌলিক কৌশল — বিন্যাস, সমাবেশ আর কবুতরের খোপ

অনেক অ্যালগরিদমের প্রথম প্রশ্ন: “সব সম্ভাব্য উত্তর পরীক্ষা করলে কতগুলো দেখতে হবে?” এর উত্তর দেয় গণনার কয়েকটি মৌলিক নিয়ম।

• গুণের নিয়ম: একটি কাজ a ভাবে, তারপর আরেকটি b ভাবে করা গেলে দুটো মিলিয়ে a × b ভাবে। bKash PIN-এর ৫টি অঙ্ক, প্রতিটি ১০ রকম — মোট 10⁵ = এক লাখ রকম PIN.
• Subset: n টি জিনিসের প্রতিটিকে “নেব / নেব না” — মোট 2ⁿ টি subset. Backtracking (পর্ব ৫৬) আর bitmask DP (পর্ব ৫৫)-এর আকার এটাই।
• Permutation (বিন্যাস — ক্রম গুরুত্বপূর্ণ): n টি আলাদা জিনিস সারিতে সাজানোর উপায় n!. n টি থেকে k টি নিয়ে সাজানোর উপায় n!/(n−k)!. পরীক্ষার খাতা কোন ক্রমে সাজানো হবে — সেটি বিন্যাস।
• Combination (সমাবেশ — ক্রম গুরুত্বহীন): n টি থেকে k টি বাছার উপায় C(n, k) = n! / (k!(n−k)!). ক্রিকেট দলের ১৫ জন থেকে ১১ জন বাছা — কে কোথায় দাঁড়াল তা নয়, কে দলে আছে তাই গুরুত্বপূর্ণ।

DSA-তে সবচেয়ে বেশি আসে C(n, 2) = n(n−1)/2 — n টি জিনিস থেকে জোড়ার সংখ্যা। একটি অনুষ্ঠানে n জন সবাই সবার সাথে একবার করে হাত মেলালে মোট হাত মেলানো C(n, 2). for i আর তার ভেতরে for j = i+1 লুপ ঠিক এই সব জোড়াই দেখে — তাই সেটি Θ(n²)। লক্ষ করুন, এটিও অংশ ৫-এর সমান্তর ধারা: (n−1) + (n−2) + … + 0.

শেষ সারিটি দেখে বুঝবেন, কেন traveling salesman-এর মতো সমস্যায় সব ক্রম পরীক্ষা করা n = ২০-এই অসম্ভব (পর্ব ৫৭ ও ৬৪)। সারণির একটি মনে রাখার নিয়ম: n ≤ ১০–১১ হলে n! চলে, n ≤ ২০–২৫ হলে 2ⁿ চলে — কনটেস্টে ইনপুটের সীমা দেখেই অনেক সময় বোঝা যায় কোন পদ্ধতি চাওয়া হচ্ছে।

Pigeonhole — কবুতরের খোপের নীতি

এটি গণিতের সবচেয়ে সরল, অথচ আশ্চর্য রকম শক্তিশালী নীতিগুলোর একটি। Pigeonhole principle: n টি খোপে n + 1 টি কবুতর রাখলে অন্তত একটি খোপে দুটি কবুতর থাকবেই। আরও সাধারণভাবে, m টি জিনিস n টি বাক্সে রাখলে কোনো একটি বাক্সে অন্তত ⌈m/n⌉ টি থাকবে। এর প্রয়োগ:

• ৩৬৭ জন মানুষের মধ্যে অন্তত দুজনের জন্মদিন একই (বছরে সর্বোচ্চ ৩৬৬টি তারিখ)।
• Hash table-এ (পর্ব ৩২) যতগুলো ঘর আছে তার চেয়ে বেশি key ঢোকালে collision অনিবার্য — hash function যত ভালোই হোক।
• কোনো compression প্রোগ্রাম সব ফাইল ছোট করতে পারে না: n-bit লম্বা ফাইল 2ⁿ টি, কিন্তু তার চেয়ে ছোট সব bit-string মিলিয়ে মাত্র 2ⁿ − 1 টি।
• কনটেস্টের একটি ক্লাসিক: n টি পূর্ণসংখ্যার যেকোনো array-তে এমন একটি পাশাপাশি অংশ আছে যার যোগফল n দিয়ে বিভাজ্য। কারণ n টি prefix sum-এর (পর্ব ১৭) n mod-মান, সাথে শূন্য-দৈর্ঘ্যের prefix-এর ০ — মোট n + 1 টি মান, অথচ ভাগশেষ মাত্র n রকম।

৯ · লুপ থেকে যোগফল — বিশ্লেষণের রেসিপি

এবার সব যন্ত্রপাতি একসাথে কাজে লাগাই। যেকোনো লুপের time complexity বের করার রেসিপি:

1. সবচেয়ে ভেতরের কাজটি (একটি তুলনা, একটি যোগ) এক একক ধরুন।
2. ভেতরের লুপ কতবার চলে, তা বাইরের লুপের চলক (i)-এর ফাংশন হিসেবে লিখুন।
3. বাইরের লুপের সব মানের ওপর Σ লিখুন।
4. পরিচিত সূত্র দিয়ে closed form বের করুন — বা অন্তত দুই দিক থেকে সীমা দিন।
5. প্রধান পদটি রেখে Θ লিখুন।

একটি উদাহরণ ধাপে ধাপে দেখুন — ভেতরের লুপ j = i থেকে শুরু হয়, তাই প্রতিবার একটু কম চলে:

1int count = 0;2for (int i = 1; i <= 4; i++)3    for (int j = i; j <= 4; j++)4        count++;5printf("count = %d\n", count);

কয়েকটি বহুল প্রচলিত লুপ-প্যাটার্ন আর তাদের যোগফল একসাথে রাখুন — বিশ্ববিদ্যালয়, চাকরি বা ইন্টারভিউর পরীক্ষায় এগুলোই ঘুরেফিরে আসে:

শেষের আগের সারিটি অনেককে চমকে দেয়: দুটি nested লুপ, অথচ সময় Θ(n)! কারণ বাইরের লুপ log n বার চললেও ভেতরের কাজ গুণোত্তর ধারায় কমছে। আর পঞ্চম সারিটি দেখতে প্রায় Θ(n²) মনে হলেও আসলে harmonic. নিচের প্রোগ্রাম তিনটি প্যাটার্ন সত্যিই চালিয়ে ধাপ গোনে, তারপর সূত্রের সাথে মেলায়:

#include <cmath>
#include <cstdio>
#include <initializer_list>
int main() {
    for (long long n : {16LL, 1000LL, 5000LL}) {
        long long halv = 0, pairs = 0, jumps = 0;
        for (long long i = n; i > 1; i /= 2) halv++;          // keep halving
        for (long long i = 0; i < n; i++)                     // every pair i < j
            for (long long j = i + 1; j < n; j++) pairs++;
        for (long long i = 1; i <= n; i++)                    // j jumps by i
            for (long long j = i; j <= n; j += i) jumps++;
        std::printf("n=%lld halvings=%lld floor(log2 n)=%d\n",
                    n, halv, int(std::floor(std::log2(double(n)))));
        std::printf("   pairs=%lld n(n-1)/2=%lld\n", pairs, n * (n - 1) / 2);
        std::printf("   jumps=%lld n*ln(n)=%.0f\n", jumps, double(n) * std::log(double(n)));
    }
}

১০ · AI-এর যুগে — AI-এর গণিত যাচাই করবেন কীভাবে

“এই কোডের complexity কত?” — প্রশ্নটি AI-কে করলে কয়েক সেকেন্ডে আত্মবিশ্বাসী উত্তর আসে। সমস্যা হলো, এই আত্মবিশ্বাস সবসময় হিসাবের ওপর দাঁড়িয়ে থাকে না। AI প্রায়ই লুপের আকার দেখে অনুমান করে (“দুটি nested লুপ, তাই O(n²)”) — অথচ আপনি অংশ ৯-এ দেখেছেন, দুটি nested লুপ Θ(n), Θ(n log n) বা Θ(n²) — যেকোনোটি হতে পারে। এই পর্বের গণিতই আপনার যাচাইয়ের অস্ত্র।

এই বিষয়ে AI সাধারণত যেসব ভুল করে

AI-এর দেওয়া হিসাব পেলে — যাচাইয়ের চেকলিস্ট

• লুপটি ছোট n-এ (১, ২, ৮, ১০) হাতে চালিয়ে গুনেছি, আর সূত্রের সাথে মিলিয়েছি
• একটি counter বসিয়ে কয়েকটি বড় n-এ চালিয়েছি — n দ্বিগুণ করলে গণনা কত গুণ হয় দেখেছি (২ গুণ → Θ(n), ৪ গুণ → Θ(n²))
• ⌊ ⌋, ⌈ ⌉ আর +১ / −১ সীমায় (n = 1, 2-এর ঘাত, 2-এর ঘাত + ১) পরীক্ষা করেছি
• সূত্রের সব মধ্যবর্তী মান যে টাইপে রাখা হচ্ছে, সেটি overflow করবে না নিশ্চিত হয়েছি
• “এটি O(…)” দাবির পক্ষে Σ বা সীমার যুক্তি নিজের ভাষায় লিখতে পারি — শুধু AI-এর কথায় বিশ্বাস করিনি