বৃদ্ধির হার আর Big-O, Ω, Θ

১ · একই কাজ, দুই পদ্ধতি — কোনটি “দ্রুত”?

একটি বোর্ড পরীক্ষার ফল প্রকাশের দিনের কথা ভাবুন। শিক্ষা বোর্ডের সার্ভারে লাখ লাখ শিক্ষার্থী একসাথে রোল নম্বর দিয়ে ফল খুঁজছেন। দুজন প্রোগ্রামার দুটি সমাধান লিখেছেন। প্রথম জনের প্রোগ্রাম nটি রেকর্ডের জন্য প্রায় 100n ধাপ নেয়। দ্বিতীয় জনের প্রোগ্রাম নেয় n² ধাপ। কোনটি ভালো?

ছোট ইনপুটে উত্তরটা উল্টো মনে হতে পারে। নিচের সারণিটি দেখুন:

n = ১০০-এর পর থেকে প্রথম পদ্ধতি চিরকালের জন্য এগিয়ে যায়, আর ব্যবধান শুধু বাড়তেই থাকে। দ্বিতীয় জন যদি ১০০ গুণ দ্রুত কম্পিউটার কেনেন? তাহলে n = 10⁶-এ তাঁর লাগবে প্রায় 10¹⁰ সরল ধাপের সময় — তবুও প্রথম জনের চেয়ে ১০০ গুণ ধীর। দ্রুত মেশিন ধ্রুবককে ছোট করে, কিন্তু বৃদ্ধির হার বদলায় না।

এই চিন্তাকে বলে asymptotic analysis — ইনপুটের আকার n অসীমের দিকে গেলে চলার সময় কীভাবে বাড়ে, সেটিই একমাত্র প্রশ্ন। পর্ব ০২-এ আমরা RAM model দেখেছি: প্রতিটি সরল কাজ (যোগ, তুলনা, একটি ঘর পড়া) এক একক সময় নেয়। তাই একটি অ্যালগরিদমের চলার সময়কে n-এর একটি ফাংশন T(n) হিসেবে লেখা যায়। এই পর্বে আমরা শিখব T(n)-এর growth rate (বৃদ্ধির হার) নিখুঁতভাবে বলার ভাষা, আর সেই ভাষার নিয়ম।

২ · ফাংশনের বৃদ্ধি — 1 থেকে n! পর্যন্ত

বাস্তবের প্রায় সব অ্যালগরিদমের চলার সময় হাতে গোনা কয়েকটি ফাংশনের কোনো একটির মতো বাড়ে। এদের নাম আর চেহারা মুখস্থ নয়, অনুভূতিতে গেঁথে নেওয়া দরকার। নিচের সারণিতে log মানে log₂ (ভিত্তি ২)।

শেষ দুটি সারি খেয়াল করুন। n = ১০০ হলেই 2ⁿ প্রায় 1.27 × 10³⁰ — মহাবিশ্বের বয়স সেকেন্ডে মাপলেও মাত্র প্রায় 4 × 10¹⁷। দাবার ছকের সেই পুরোনো গল্পটি মনে আছে? প্রথম ঘরে একটি ধানের দানা, প্রতি ঘরে দ্বিগুণ — ৬৪তম ঘরে লাগে 2⁶³টি দানা, যা পৃথিবীর সব গোলার ধানেও হয় না। Exponential বৃদ্ধি এমনই।

কনটেস্টের হাতের নিয়ম — এক সেকেন্ডে প্রায় 10⁸

একটি আধুনিক কম্পিউটার C++-এ এক সেকেন্ডে মোটামুটি 10⁸ (দশ কোটি) সরল ধাপ চালাতে পারে — যোগ, তুলনা, array পড়া। এটি নিখুঁত মাপ নয়: ধাপের ধরন, cache, ভাষা ভেদে সংখ্যাটি কয়েক গুণ কম-বেশি হয়। Python সাধারণত এর চেয়ে কয়েক ডজন গুণ ধীর। তবু প্রোগ্রাম লেখার আগেই সিদ্ধান্ত নেওয়ার জন্য এটি দারুণ কাজের। Codeforces বা ICPC-ধাঁচের সমস্যায় প্রশ্নে n-এর সীমা দেখেই বোঝা যায় কোন complexity চাওয়া হচ্ছে:

একটি উদাহরণে ব্যবহারটি দেখুন। ধরুন প্রশ্নে বলা আছে: একটি সরলরেখায় n-টি বাসস্টপের অবস্থান দেওয়া, n ≤ 2 × 10⁵; বের করতে হবে কতগুলো জোড়া স্টপের দূরত্ব k-এর চেয়ে কম। প্রথমেই মাথায় আসে সব জোড়া পরীক্ষা — n(n−1)/2 ≈ 2 × 10¹⁰ জোড়া, অর্থাৎ কয়েক মিনিট। কোড লেখার আগেই তাই বুঝে যান যে এই পথ বন্ধ। দরকার O(n log n) বা O(n) — যেমন আগে sort করে two pointer বা binary search (পর্ব ১৬ ও ১৮)। উল্টো দিকে কোনো প্রশ্নে n ≤ 18 দেখলে সন্দেহ করুন যে সব subset পরীক্ষা বা bitmask DP (পর্ব ৫৫) চাওয়া হচ্ছে — নইলে সীমা এত ছোট রাখার কারণ নেই। সীমা নিজেই সমাধানের ইঙ্গিত।

এবার নিজে দেখুন। নিচের ছোট টুলটিতে “চালিয়ে দেখুন” চাপুন, তারপর স্লাইডার টেনে n বদলান। প্রতিটি বৃদ্ধির হারে মোট ধাপ, 10⁸ ধাপ/সেকেন্ড ধরে আনুমানিক সময় আর একটি log-স্কেলের দণ্ড দেখাবে। সবুজ মানে এক সেকেন্ডের মধ্যে, কমলা মানে ১০০ সেকেন্ডের মধ্যে, লাল মানে আশা নেই।

const NS = [10, 20, 50, 100, 1e3, 1e4, 1e5, 1e6, 1e7, 1e8, 1e9];
const FNS = [["1", n => 1], ["log n", n => Math.log2(n)], ["sqrt n", n => Math.sqrt(n)],
  ["n", n => n], ["n log n", n => n * Math.log2(n)], ["n^2", n => n * n], ["n^3", n => n ** 3],
  ["2^n", n => 2 ** n], ["n!", n => { let p = 1; for (let k = 2; k <= n && p < 1e300; k++) p *= k; return p; }]];
const fmt = x => !isFinite(x) || x >= 1e300 ? "> 1e300" : x < 1e6 ? (+x.toFixed(1)).toLocaleString("en") : x.toExponential(1).replace("e+", "e");
const when = s => s < 1e-3 ? "< 1 ms" : s < 1 ? (s * 1e3).toFixed(0) + " ms" : s < 60 ? s.toFixed(1) + " s"
  : s < 3600 ? (s / 60).toFixed(1) + " min" : s < 86400 ? (s / 3600).toFixed(1) + " h"
  : s < 3.156e7 ? (s / 86400).toFixed(0) + " days" : fmt(s / 3.156e7) + " years";
function draw(n) {
  document.getElementById("nv").textContent = n.toLocaleString("en");
  document.getElementById("rows").innerHTML = FNS.map(([lab, f]) => {
    const ops = f(n), s = ops / 1e8, w = Math.min(100, Math.log10(ops + 1) / 18 * 100);
    const col = s <= 1 ? "#16a34a" : s <= 100 ? "#d97706" : "#dc2626";
    return `<tr><td>${lab}</td><td>${fmt(ops)}</td><td>${when(s)}</td>` +
      `<td><div style="height:10px;width:${w}%;background:${col}"></div></td></tr>`;
  }).join("");
}
const slider = document.getElementById("ns");
slider.oninput = () => draw(NS[slider.value]);
draw(NS[slider.value]);
for (const n of [1e5, 1e6]) console.log(`n = ${fmt(n)}: n log n -> ${when(n * Math.log2(n) / 1e8)}, n^2 -> ${when(n * n / 1e8)}`);

৩ · Big-O, Ω, Θ — c আর n₀ দিয়ে আনুষ্ঠানিক সংজ্ঞা

“প্রায় n²-এর মতো বাড়ে” কথাটি বুঝতে সহজ, কিন্তু প্রমাণে চলে না। তাই গণিতের ভাষায় নিখুঁত সংজ্ঞা দরকার। সব সংজ্ঞায় f(n) আর g(n) এমন ফাংশন, যারা বড় n-এ ঋণাত্মক নয় (চলার সময় কখনো ঋণাত্মক হয় না)।

সংজ্ঞার দুটি অংশের ভূমিকা আলাদা। c ধ্রুবক গুণককে “মাফ” করে দেয় — 3n² আর n² একই শ্রেণির। n₀ ছোট n-এর গোলমালকে মাফ করে — শুরুতে f একটু বেশি হলেও চলে, শুধু একটি বিন্দুর পর থেকে চিরকাল সীমার নিচে থাকতে হবে। নিচের ছবিটি দেখুন:

এবার সবচেয়ে কাজের দক্ষতা: সংজ্ঞা থেকে সরাসরি প্রমাণ। দাবি: f(n) = 3n² + 5n + 2 = Θ(n²). আমাদের তিনটি সংখ্যা খুঁজে বের করতে হবে — c₁, c₂ আর n₀. ধাপে ধাপে দেখুন:

খুঁজতে হবে c₁ > 0, c₂ > 0, n₀ — যাতে সব n ≥ n₀-এর জন্য

    c₁ · n²  ≤  3n² + 5n + 2  ≤  c₂ · n²

বাঁ অংশ = Ω(n²),  ডান অংশ = O(n²)

n ≥ 1 হলে:   5n ≤ 5n²    আর    2 ≤ 2n²

3n² + 5n + 2  ≤  3n² + 5n² + 2n²  =  10n²

=> c₂ = 10,  n₀ = 1

n = 1  :  f = 3 + 5 + 2       = 10    ≤  10     ✓ (ঠিক সমান)
n = 2  :  f = 12 + 10 + 2     = 24    ≤  40     ✓
n = 10 :  f = 300 + 50 + 2    = 352   ≤  1000   ✓
(যাচাই প্রমাণ নয় — শুধু ভুল ধরার সহায়ক)

n ≥ 1 হলে 5n + 2 > 0, তাই

3n² + 5n + 2  ≥  3n²

=> c₁ = 3

সব n ≥ 1-এর জন্য:   3n²  ≤  3n² + 5n + 2  ≤  10n²

c₁ = 3,  c₂ = 10,  n₀ = 1   =>   f(n) = Θ(n²)   ∎

অন্য বাছাইও চলে:  n ≥ 6 হলে 5n + 2 ≤ n²,
তাই c₂ = 4, n₀ = 6 দিয়েও প্রমাণ হয়।

ধরি কোনো c, n₀ আছে যাতে সব n ≥ n₀-এ  3n² + 5n + 2 ≤ c · n

তাহলে  3n² ≤ c · n   =>   n ≤ c / 3

কিন্তু n = max(n₀, c) নিলে n > c / 3 — বিরোধ!
=> এমন c নেই, তাই f(n) ≠ O(n)

৪ · little-o, little-ω আর limit test

O(g) বলে “f, g-এর চেয়ে দ্রুত বাড়ে না” — সমানতালে বাড়লেও চলে। কিন্তু কখনো আমরা বলতে চাই “f কঠোরভাবে ধীরে বাড়ে”, যেমন n বনাম n². তার জন্য ছোট হাতের চিহ্ন:

• little-o: f(n) = o(g(n)), যদি প্রতিটি ধ্রুবক c > 0-এর জন্য এমন n₀ থাকে যে সব n ≥ n₀-এ 0 ≤ f(n) < c · g(n). পার্থক্যটি সূক্ষ্ম: O-তে “কোনো একটি c” পেলেই হয়; o-তে c যত ছোটই নিন, একসময় f তার নিচে নামবেই।
• little-ω: f(n) = ω(g(n)), যদি প্রতিটি c > 0-এর জন্য একসময় f(n) > c · g(n). অর্থাৎ f কঠোরভাবে দ্রুত বাড়ে। g = o(f) আর f = ω(g) একই কথা।

পাঁচটি চিহ্নকে সংখ্যার তুলনার সাথে মিলিয়ে মনে রাখা যায় — শুধু মনে রাখবেন, এটি উপমা, হুবহু এক নয়:

Limit test — ভাগ করে দেখুন

দুটি ফাংশন তুলনার সবচেয়ে দ্রুত উপায় হলো তাদের ভাগফলের limit নেওয়া। ধরুন L = lim_n→∞ f(n) / g(n) আছে। তাহলে:

কয়েকটি উদাহরণ, প্রয়োজনে L’Hôpital-এর নিয়ম (লব আর হর দুটোই অসীমে গেলে দুটির derivative-এর ভাগফল নেওয়া) ব্যবহার করে:

• (3n² + 5n + 2) / n² = 3 + 5/n + 2/n² → 3. যেহেতু 0 < 3 < ∞, তাই Θ(n²) — আগের প্রমাণের সাথে মিলে গেল, অনেক কম পরিশ্রমে।
• ln n / √n: দুটোই অসীমে যায়। derivative নিলে (1/n) / (1/(2√n)) = 2/√n → 0. তাই log n = o(√n) — যেকোনো log যেকোনো ধনাত্মক ঘাতের চেয়ে ধীরে বাড়ে।
• n² / 2ⁿ: দুবার L’Hôpital নিলে 2 / (2ⁿ (ln 2)²) → 0. তাই n² = o(2ⁿ); একইভাবে যেকোনো n^k = o(2ⁿ).
• 2ⁿ / 3ⁿ = (2/3)ⁿ → 0. তাই 2ⁿ = o(3ⁿ) — exponential-এর ভিত্তি বদলালে শ্রেণিই বদলে যায়!
• 2ⁿ / n! = (2/1)(2/2)(2/3)…(2/n) ≤ 2 · (2/n) = 4/n → 0. তাই 2ⁿ = o(n!).

এভাবে প্রচলিত ফাংশনগুলোকে একটি শিকলে সাজানো যায়, যেখানে প্রতিটি পরেরটির little-o:

৫ · হিসাবের নিয়ম — যোগ, গুণ, ছোট পদ আর log-এর ভিত্তি

প্রতিবার c আর n₀ খুঁজে প্রমাণ করতে হলে বিশ্লেষণ খুব ধীর হতো। সৌভাগ্যক্রমে কয়েকটি নিয়ম সংজ্ঞা থেকেই প্রমাণ হয়, আর এগুলো দিয়েই বাস্তবের প্রায় সব হিসাব হয়ে যায়।

যোগের নিয়ম কেন সত্য: f ≤ c₁·F আর g ≤ c₂·G হলে f + g ≤ c₁F + c₂G ≤ (c₁ + c₂) · max(F, G). তাই n log n সময়ের sort-এর পর n সময়ের একটি লুপ চালালে মোট O(n log n + n) = O(n log n). গুণের নিয়মও একইভাবে: f · g ≤ (c₁c₂) · F·G.

log-এর ভিত্তি কেন গুরুত্বহীন: log₂ n = log₁₀ n / log₁₀ 2 ≈ 3.32 · log₁₀ n. দুটির পার্থক্য শুধু একটি ধ্রুবক গুণক, আর ধ্রুবক তো আমরা বাদই দিই। কিন্তু সাবধান — ঘাতে ভিত্তি গুরুত্বপূর্ণ। 2ⁿ আর 4ⁿ = 2²ⁿ আলাদা শ্রেণি (ভাগফল 2ⁿ, ধ্রুবক নয়)। একইভাবে 2^{log₂ n} = n, কিন্তু 2^{log₄ n} = √n.

একটি পূর্ণ উদাহরণ — নিয়মগুলো একসাথে

ধরুন একটি ফাংশন bKash-এর মতো কোনো লেনদেন-তালিকার n-টি অঙ্ক নিয়ে দেখে, কোন দুটি লেনদেনের যোগফল ঠিক x টাকা। কোডের কাঠামো এমন (Pseudocode, 1-based):

sort(a[1..n])                          // Θ(n log n)
for i = 1 to n:                        // n বার
    if binary_search(a, x - a[i]):     // প্রতিবার Θ(log n)
        count = count + 1
for i = 1 to 100:                      // প্রথম ১০০টির রিপোর্ট
    for j = 1 to 100: compare(a[i], a[j])   // 10⁴ বার — n-এর ওপর নির্ভর করে না

এবার নিয়মগুলো একে একে লাগাই। প্রথম লাইন Θ(n log n). দ্বিতীয় অংশে বাইরে n বার, প্রতিবার ভেতরে Θ(log n) — গুণের নিয়মে Θ(n log n). তৃতীয় অংশ 10⁴টি তুলনা, n যত বড়ই হোক সংখ্যাটি একই — অর্থাৎ Θ(1). তিনটি অংশ পরপর চলে, তাই যোগের নিয়মে মোট Θ(n log n + n log n + 1) = Θ(n log n). খেয়াল করুন, তৃতীয় অংশে দুটি nested লুপ থাকলেও সেটি n² নয় — লুপের সংখ্যা নয়, লুপ কতবার চলে আর সেটি n-এর ওপর নির্ভর করে কি না, সেটিই আসল।

৬ · লুপ গুনে complexity — পাঁচটি কাঠামো

বাস্তব কোডের বিশ্লেষণ মানে মূলত লুপ গোনা: সবচেয়ে ভেতরের কাজটি মোট কতবার হয়? নিয়মগুলো এবার কাজে লাগাই।

(ক) পরপর লুপ — যোগ

for i = 1 to n:      do A        // n বার
for j = 1 to n*n:    do B        // n² বার
মোট = n + n² = Θ(n²)            // বড়টি টেকে

(খ) স্বাধীন nested লুপ — গুণ

বাইরের লুপ n বার, প্রতিবার ভেতরের লুপ m বার: মোট n · m. দুটোই n হলে Θ(n²)। যেমন একটি ক্লাসের সব জোড়া ছাত্রের রোল মেলানো।

(গ) নির্ভরশীল ভেতরের লুপ — j চলে i থেকে n

এখানে ভেতরের লুপের দৈর্ঘ্য প্রতিবার বদলায়, তাই সরাসরি গুণ করা যায় না। ছোট n নিয়ে হাতে গুনি — n = 4:

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

(ঘ) প্রতিবার অর্ধেক — log n

যে লুপে চলকটি প্রতিবার অর্ধেক (বা দ্বিগুণ) হয়, সেটি কতবার চলে? n = 20 নিয়ে দেখুন — পাশে i-এর binary রূপও আছে:

1int cnt = 0;2for (int i = n; i >= 1; i /= 2)3    cnt++;4printf("cnt = %d\n", cnt);

এই কাঠামোই binary search-এর (পর্ব ১৮) প্রাণ: প্রতি ধাপে খোঁজার জায়গা অর্ধেক। ফোনবুকে নাম খোঁজার সময় আপনিও মাঝখান থেকে খোলেন, তারপর বাকি অর্ধেকে যান — ১০০০ পাতার বইয়ে ১০ বারের মতো খুললেই পাতা পেয়ে যান।

(ঙ) i · i ≤ n পর্যন্ত — √n

কোনো সংখ্যা মৌলিক কি না যাচাই করতে √n পর্যন্ত ভাগ করলেই চলে, কারণ n = a · b হলে a আর b-এর অন্তত একটি ≤ √n. লুপটি দেখতে এমন — n = 30 নিয়ে গুনি:

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

এক নজরে — লুপের কাঠামো আর তার complexity

৭ · নিজে গুনে দেখুন — দ্বিগুণ n, কত গুণ কাজ?

তত্ত্ব হলো। এবার পরীক্ষা। নিচের প্রোগ্রামটি ছয় ধরনের লুপের ভেতরের কাজ সত্যিই গুনে দেখে — n = 250, 500, 1000, 2000-এর জন্য। শেষ কলামে আছে ratio = গণনা(2000) / গণনা(1000). এটিই “doubling test”: n দ্বিগুণ করলে কাজ কত গুণ হয়, সেটি দেখেই বৃদ্ধির হার চেনা যায়। আপনার ভাষার ট্যাবটি বেছে নিন:

#include <cstdio>
#include <vector>
using ll = long long;
ll lin(ll n)  { ll c = 0; for (ll i = 0; i < n; i++) c++; return c; }
ll quad(ll n) { ll c = 0; for (ll i = 0; i < n; i++) for (ll j = 0; j < n; j++) c++; return c; }
ll tri(ll n)  { ll c = 0; for (ll i = 0; i < n; i++) for (ll j = i; j < n; j++) c++; return c; }
ll halv(ll n) { ll c = 0; for (ll i = n; i >= 1; i /= 2) c++; return c; }
ll root(ll n) { ll c = 0; for (ll i = 1; i * i <= n; i++) c++; return c; }
ll nlog(ll n) { ll c = 0; for (ll i = 0; i < n; i++) for (ll j = n; j >= 1; j /= 2) c++; return c; }
int main() {
    std::vector<ll> ns = {250, 500, 1000, 2000};
    std::vector<std::pair<const char*, ll (*)(ll)>> loops = {
        {"n", lin}, {"n^2", quad}, {"n(n+1)/2", tri}, {"log n", halv}, {"sqrt n", root}, {"n log n", nlog}};
    std::printf("%-10s", "loop");
    for (ll n : ns) std::printf("%10lld", n);
    std::printf("%8s\n", "ratio");
    for (auto [label, f] : loops) {
        std::vector<ll> cnt; std::printf("%-10s", label);
        for (ll n : ns) { cnt.push_back(f(n)); std::printf("%10lld", cnt.back()); }
        std::printf("%8.2f\n", (double)cnt[3] / cnt[2]);
    }
}

loop             250       500      1000      2000   ratio
n                250       500      1000      2000    2.00
n^2            62500    250000   1000000   4000000    4.00
n(n+1)/2       31375    125250    500500   2001000    4.00
log n              8         9        10        11    1.10
sqrt n            15        22        31        44    1.42
n log n         2000      4500     10000     22000    2.20

def lin(n):                         # একটি লুপ
    return sum(1 for i in range(n))
def quad(n):                        # দুটি পূর্ণ nested লুপ
    return sum(1 for i in range(n) for j in range(n))
def tri(n):                         # ভেতরের লুপ i থেকে n পর্যন্ত
    return sum(1 for i in range(n) for j in range(i, n))
def halv(n):                        # প্রতিবার অর্ধেক
    c, i = 0, n
    while i >= 1: c, i = c + 1, i // 2
    return c
def root(n):                        # i*i <= n পর্যন্ত
    c, i = 0, 1
    while i * i <= n: c, i = c + 1, i + 1
    return c
def nlog(n): return n * halv(n)     # বাইরে n বার, ভেতরে অর্ধেক-লুপ

ns = [250, 500, 1000, 2000]
print(f"{'loop':<10}" + "".join(f"{n:>10}" for n in ns) + f"{'ratio':>8}")
for label, f in [("n", lin), ("n^2", quad), ("n(n+1)/2", tri),
                 ("log n", halv), ("sqrt n", root), ("n log n", nlog)]:
    cnt = [f(n) for n in ns]
    print(f"{label:<10}" + "".join(f"{c:>10}" for c in cnt) + f"{cnt[-1] / cnt[-2]:>8.2f}")

loop             250       500      1000      2000   ratio
n                250       500      1000      2000    2.00
n^2            62500    250000   1000000   4000000    4.00
n(n+1)/2       31375    125250    500500   2001000    4.00
log n              8         9        10        11    1.10
sqrt n            15        22        31        44    1.42
n log n         2000      4500     10000     22000    2.20

ratio কলামটি পড়ুন। Θ(n) দ্বিগুণ হয় (2.00), Θ(n²) চার গুণ (4.00) — নির্ভরশীল লুপ n(n+1)/2-ও চার গুণ, কারণ ½ ধ্রুবক ratio-তে কেটে যায়। Θ(log n) গুণ হয় না, শুধু এক যোগ হয় (10 → 11). Θ(√n) বাড়ে √2 ≈ 1.41 গুণ (31 → 44, ⌊√⌋-এর কারণে 1.42). আর Θ(n log n)-এর ratio 2-এর একটু বেশি (2.20) — n দ্বিগুণ, log n-এ সামান্য বৃদ্ধি। সাধারণ নিয়ম: n দ্বিগুণে কাজ প্রায় 2^k গুণ হলে বৃদ্ধি Θ(n^k).

৮ · প্রচলিত ভুল ধারণা — আর পরের পর্বের দরজা

ভুল ১: “O মানেই worst case”

না। O, Ω, Θ হলো ফাংশনের সীমা বলার ভাষা — কোন ফাংশনের কথা বলছেন, সেটি আলাদা প্রশ্ন। Insertion sort-এর (পর্ব ২০) কথা ধরুন। আগে থেকে সাজানো array-তে সে নেয় Θ(n) সময় — এটি তার best case. উল্টো করে সাজানো array-তে নেয় Θ(n²) — এটি তার worst case. দুটি আলাদা ফাংশন, আর প্রতিটির জন্যই O, Ω, Θ তিনটি বলা যায়। “Insertion sort-এর worst case Θ(n²)” আর “best case Θ(n)” — দুটোই নিখুঁত বাক্য। “সব ইনপুটে insertion sort O(n²) আর Ω(n)” — এটিও সত্য। Best, worst আর average case কীভাবে আলাদা করে বিশ্লেষণ করতে হয়, আর মেমরির হিসাব — space complexity — পুরোটাই পর্ব ০৫-এর বিষয়।

ভুল ২: দৈনন্দিন কথায় O বলে Θ বোঝানো

প্রোগ্রামাররা প্রায়ই বলেন “merge sort O(n log n)” — বোঝাতে চান Θ(n log n). এটি সাধারণত ক্ষতিকর নয়, তবে মনে রাখুন: O শুধু upper bound. “Binary search O(n)” কথাটিও গাণিতিকভাবে সত্য (log n ≤ n), কিন্তু প্রায় অর্থহীন — যেমন “ঢাকা থেকে সিলেট ১০,০০০ কিলোমিটারের কম” সত্য, কিন্তু কাজে লাগে না। পরীক্ষায় বা ইন্টারভিউতে সবচেয়ে আঁটসাঁট সীমাটি বলুন, আর প্রয়োজনে স্পষ্ট করে Θ লিখুন। একইভাবে lower bound Ω কোনো সমস্যার জন্যও বলা যায় — যেমন তুলনা-ভিত্তিক যেকোনো sort-এর worst case Ω(n log n), যার প্রমাণ পর্ব ২৪-এ।

ভুল ৩: “ধ্রুবক কখনো গুরুত্বপূর্ণ নয়”

বিশ্লেষণে ধ্রুবক বাদ দিই, কিন্তু বাস্তবে ধ্রুবক সময় খায়। 100n বনাম n²-এর সারণিতে n < 100 হলে n²-ই জিতেছিল। এজন্যই বাস্তবের sort লাইব্রেরিগুলো ছোট অংশে (কয়েক ডজন উপাদান পর্যন্ত) insertion sort চালায় — Θ(n²) হলেও তার ধ্রুবক খুব ছোট। আবার array আর linked list দুটোতেই সব উপাদান ঘুরে দেখা Θ(n), কিন্তু array সাধারণত কয়েক গুণ দ্রুত, কারণ পাশাপাশি ঘর CPU-র cache-এ একসাথে আসে (পর্ব ১০ ও ১২)। সিদ্ধান্তের ক্রম: আগে সঠিক শ্রেণি বাছুন, তারপর একই শ্রেণির মধ্যে ধ্রুবক মাপুন।

ভুল ৪: “O(1) মানে তাৎক্ষণিক”

O(1) মানে শুধু “n-এর ওপর নির্ভর করে না”। একটি লুপ যদি সবসময় ঠিক 10⁹ বার চলে, সেটিও O(1) — কিন্তু কয়েক সেকেন্ড লাগবে। আবার hash table-এর (পর্ব ৩২) “O(1)” আসলে গড় হিসাব; খারাপ ইনপুটে একটি খোঁজ অনেক ধীর হতে পারে।

ভুল ৫: “n মানে সবসময় সংখ্যাটি নিজে”

n হলো ইনপুটের আকার। একটি সংখ্যা N মৌলিক কি না, √N পর্যন্ত ভাগ করে দেখা মানে O(√N) ধাপ। কিন্তু N লিখতে লাগে মাত্র প্রায় log₂ N বিট। বিটের সংখ্যা b ধরলে √N = 2^b/2 — ইনপুটের আকারের তুলনায় exponential! এই সূক্ষ্মতা পরে knapsack-এর DP (পর্ব ৫৩) আর P বনাম NP (পর্ব ৬৪) বুঝতে লাগবে।

৯ · AI-এর যুগে complexity যাচাই

AI-কে কোড দিয়ে জিজ্ঞেস করলে এক সেকেন্ডে উত্তর আসে: “এর time complexity O(n log n)”. আত্মবিশ্বাসী ভাষা, পরিষ্কার ব্যাখ্যা — কিন্তু প্রায়ই ভুল। কারণ AI অনেক সময় কোডের চেহারা দেখে অনুমান করে (“দুটি লুপ, তাই n²”), ধাপ গোনে না। কনটেস্টে এর দাম একটি “Time Limit Exceeded”, ইন্টারভিউতে একটি ভুল উত্তর।

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

• ছোট একটি n (৪ বা ৮) নিয়ে ভেতরের কাজ হাতে গুনেছি, আর AI-এর সূত্রে বসিয়ে মিলিয়েছি
• কোডে একটি counter বসিয়ে n আর 2n-এ চালিয়েছি — ratio দেখে শ্রেণি মিলিয়েছি (doubling test)
• সবচেয়ে বড় সীমার ইনপুট বানিয়ে আসল সময় মেপেছি, শুধু নমুনা ইনপুটে নয়
• দ্রুত সমাধানের ফল একটি সরল brute-force সমাধানের সাথে অনেক এলোমেলো ছোট ইনপুটে মিলিয়েছি (stress test)
• n = 0, n = 1, সব উপাদান সমান, আগে থেকে সাজানো — এমন কিনারার ইনপুটেও চালিয়েছি
• নিজের ভাষায় বলতে পারি কেন সীমাটি Θ, শুধু O নয়