little-o, little-omega ও টাইট বাউন্ড

Distinguishing strict bounds (o, ω) from non-strict bounds (O, Ω)

৯ মিনিট পড়া মধ্যম · Intermediate Python কোডসহ সম্পূর্ণ বাংলায়

এক নজরে · TL;DR

$O(g(n))$ মানে "$g(n)$-এর সমান বা তার চেয়ে ধীরে বাড়ে" (অ-কঠোর) — কিন্তু $o(g(n))$ মানে "$g(n)$-এর চেয়ে কঠোরভাবে ধীরে বাড়ে" — পার্থক্যটি ঠিক $\le$ বনাম $<$-এর মতো।
সবচেয়ে পরিষ্কার পরীক্ষা হলো সীমা (limit): $\lim_{n\to\infty} \frac{f(n)}{g(n)}$ যদি $0$ হয়, তাহলে $f = o(g)$; যদি একটি ধনাত্মক সসীম ধ্রুবক হয়, তাহলে $f = \Theta(g)$ (টাইট, কিন্তু $o$ নয়); আর যদি $\infty$ হয়, তাহলে $f = \omega(g)$।
নিচের কোড সেলে তিনটি জোড়া $(f, g)$-এর জন্য এই অনুপাত সরাসরি গণনা করে দেখানো হয়েছে — একটি সত্যিকারের সংখ্যাসূচক প্রমাণ, শুধু তত্ত্ব নয়।
$\Theta(g(n))$ হওয়া মানেই $o(g(n))$ নয় — এই দুটোকে গুলিয়ে ফেলা এই বিষয়ের সবচেয়ে সাধারণ ভুল।

এই পাঠে যা শিখবেন

little-o ও little-omega-এর সীমা-ভিত্তিক সংজ্ঞা, এবং এদের সাথে big-O/Omega-এর পার্থক্য
কেন $\Theta$ (টাইট বাউন্ড) হওয়া এবং $o$ (কঠোর বাউন্ড) হওয়া দুটি সম্পূর্ণ ভিন্ন দাবি
$f(n)/g(n)$ অনুপাতের সীমা গণনা করে একটি সম্পর্ক ($o$, $\Theta$, নাকি $\omega$) কম্পিউটেশনালি শনাক্ত করা
এই সূক্ষ্ম পার্থক্যগুলো কেন রিকারেন্স সমাধানে (M3) এবং মাস্টার থিওরেমের রেগুলারিটি কন্ডিশনে (L13) গুরুত্বপূর্ণ

১ · O বনাম o — অ-কঠোর বনাম কঠোর

L06-এ আমরা দেখেছি $f(n) = O(g(n))$ মানে $f(n) \le c \cdot g(n)$ — এটি অ-কঠোর ($\le$), অর্থাৎ $f(n)$ এবং $g(n)$ একই গ্রোথ ক্লাসেও থাকতে পারে (যেমন $f(n)=2n^2, g(n)=n^2$)। কিন্তু little-o এর দাবি অনেক শক্তিশালী — এটি বলে $f(n)$ প্রকৃতপক্ষেই $g(n)$-এর চেয়ে ধীরে বাড়ে:

$$f(n) = o(g(n)) \iff \lim_{n\to\infty} \frac{f(n)}{g(n)} = 0$$

সমতুল্য একটি $\forall c$-ভিত্তিক সংজ্ঞাও আছে (কিছু টেক্সটবই এটি ব্যবহার করে): প্রতিটি ধনাত্মক ধ্রুবক $c$-এর জন্য (যত ছোটই হোক না কেন) এমন $n_0$ থাকে যেন $f(n) < c \cdot g(n)$ সব $n \ge n_0$-এ সত্য। লক্ষ্য করুন পার্থক্যটি O-এর সংজ্ঞার সাথে — O-তে "একটি" $c$ পেলেই চলে, কিন্তু o-তে "প্রতিটি" $c$-এর জন্য (এমনকি অতি ক্ষুদ্র $c=0.0001$-এর জন্যও) কাজ করতে হয়। এটিই সীমা $=0$ হওয়ার সমতুল্য।

একইভাবে little-omega ($\omega$) হলো $\Omega$-এর কঠোর সংস্করণ:

$$f(n) = \omega(g(n)) \iff \lim_{n\to\infty} \frac{f(n)}{g(n)} = \infty$$

আর মাঝখানে থাকে টাইট $\Theta$ — যখন সীমাটি একটি ধনাত্মক, সসীম ধ্রুবকে স্থির হয়:

$$f(n) = \Theta(g(n)) \iff \lim_{n\to\infty} \frac{f(n)}{g(n)} = c, \quad 0 < c < \infty$$

একই "f(n)/g(n)" গণনা থেকে তিনটি ভিন্ন সিদ্ধান্তে পৌঁছানো যায় — শুধু সীমার চূড়ান্ত মান দেখে।

২ · কোড সেল — অনুপাত গণনা করে সম্পর্ক শনাক্ত করা

নিচে তিনটি জোড়া $(f, g)$-এর জন্য $n$ বাড়ার সাথে সাথে $f(n)/g(n)$ কীভাবে বদলায় তা সরাসরি গণনা করা হয়েছে: $(n,\ n^2)$ — প্রত্যাশা little-o; $(2n^2+3n,\ n^2)$ — প্রত্যাশা টাইট $\Theta$ (কিন্তু $o$ নয়); এবং $(n^2,\ n)$ — প্রত্যাশা little-omega।

Python

def f1(n): return n            # little-o প্রত্যাশা: n = o(n^2)
def g1(n): return n ** 2

def f2(n): return 2 * n**2 + 3 * n   # টাইট Theta প্রত্যাশা: Θ(n^2), o নয়
def g2(n): return n ** 2

def f3(n): return n ** 2       # little-omega প্রত্যাশা: n^2 = ω(n)
def g3(n): return n

sizes = [10, 100, 1_000, 10_000, 100_000, 1_000_000]

print(f"{'n':>10} | {'n/n^2':>12} | {'(2n^2+3n)/n^2':>16} | {'n^2/n':>12}")
for n in sizes:
    r1 = f1(n) / g1(n)
    r2 = f2(n) / g2(n)
    r3 = f3(n) / g3(n)
    print(f"{n:>10} | {r1:>12.6f} | {r2:>16.6f} | {r3:>12.1f}")

print("\nn বাড়ার সাথে সাথে প্রতিটি অনুপাতের প্রবণতা:")
print("n / n^2       ->  0-এর দিকে যাচ্ছে   => n = o(n^2)")
print("(2n^2+3n)/n^2 ->  2-এর দিকে যাচ্ছে   => Θ(n^2), কিন্তু o(n^2) নয়")
print("n^2 / n       ->  অসীমের দিকে যাচ্ছে => n^2 = ω(n)")

দ্বিতীয় কলামে লক্ষ্য করুন — $\frac{2n^2+3n}{n^2} = 2 + \frac{3}{n}$ কখনোই ঠিক $0$ হয় না, বরং $n$ বাড়ার সাথে সাথে ধ্রুবক $2$-এর দিকে এগিয়ে যায় ($n=10$-এ $2.3$, $n=1{,}000{,}000$-এ প্রায় $2.000003$)। এই আচরণটিই $\Theta$-এর সংজ্ঞা পূরণ করে — কিন্তু যেহেতু সীমা $0$ নয়, তাই $2n^2+3n \ne o(n^2)$। প্রথম কলামে $n/n^2=1/n$ সত্যিই $0$-এর দিকে যাচ্ছে (little-o), আর তৃতীয় কলামে $n^2/n=n$ কোনো সীমার কাছে না গিয়ে সরাসরি বেড়েই চলেছে (little-omega)।

মূল কথা · Key takeaway

"$f$-এর গ্রোথ $g$-এর $O$" বলা এবং "$f$-এর গ্রোথ $g$-এর $o$" বলা — এই দুটো সম্পূর্ণ ভিন্ন শক্তির দাবি। যখনই সম্ভব, $f(n)/g(n)$-এর সীমা গণনা করুন — এটি এক ধাক্কায় বলে দেয় সম্পর্কটি $o$ (কঠোরভাবে ধীর), $\Theta$ (টাইট, সমান ক্লাস), নাকি $\omega$ (কঠোরভাবে দ্রুত)। M3-এর রিকারেন্স সমাধানে এবং L13-এর মাস্টার থিওরেমের তৃতীয় কেসে (regularity condition) এই পার্থক্যটি সরাসরি ব্যবহৃত হবে।

ভাবনার প্রশ্ন

প্রতিটি প্রশ্ন নিজে কিছুক্ষণ ভাবুন — তারপর "→ উত্তর" চাপুন।

প্র ০১ $f(n) = n^2$ এবং $g(n) = n^2$ হলে, $f(n) = O(g(n))$ কি সত্য? $f(n) = o(g(n))$ কি সত্য?

$O(g(n))$ সত্য — $c=1, n_0=1$ নিলে $n^2 \le 1 \cdot n^2$ সবসময় সত্য (সমতা দিয়ে হলেও)। কিন্তু $o(g(n))$ মিথ্যা — কারণ $\lim_{n\to\infty} \frac{n^2}{n^2} = 1 \ne 0$। এটিই মূল পার্থক্য: $O$ সমতা (equality) মেনে নেয়, কিন্তু $o$ কঠোরভাবে ছোট হওয়া দাবি করে। একই ফাংশনের সাথে নিজেকে তুলনা করলে কখনোই $o$ সত্য হতে পারে না, কিন্তু $O$ সবসময় সত্য।

প্র ০২ কোড সেলে $(2n^2+3n)/n^2$ অনুপাত $n$ বাড়ার সাথে সাথে কমছে ($2.3 \to 2.000003$) — তাহলে কি এটি little-o-এর সংজ্ঞা পূরণ করে না, যেহেতু অনুপাতটি ছোট হচ্ছে?

না — little-o-এর শর্ত হলো সীমাটি ঠিক শূন্যে পৌঁছাতে হবে, "ছোট হচ্ছে" যথেষ্ট নয়। এখানে অনুপাতটি $2$-এর দিকে এগোচ্ছে, শূন্যের দিকে নয় ($\lim_{n\to\infty} (2+3/n) = 2$)। একটি ধ্রুবক ($\ne 0$)-এ পৌঁছানো মানেই সম্পর্কটি টাইট $\Theta$, little-o নয়। little-o দাবি করতে হলে অনুপাতকে সত্যিই $0$-এ অভিসৃত (converge) হতে হবে, শুধু কমতে থাকলেই চলবে না।

প্র ০৩ যদি $f(n)/g(n)$-এর সীমা $n\to\infty$ হলে না থাকে (যেমন এটি দোদুল্যমান/oscillate করে, কোনো নির্দিষ্ট মানের কাছে না গিয়ে), তাহলে কি $f = O(g)$, $o(g)$, বা $\Theta(g)$ — এর কোনোটিই বলা যাবে না?

সীমা না থাকলে $o$, $\omega$, এবং $\Theta$-এর সীমা-ভিত্তিক সংজ্ঞা প্রযোজ্য নয় (এগুলো ধরেই নেয় সীমাটি অস্তিত্বশীল)। কিন্তু $O$ এবং $\Omega$-এর মূল সংজ্ঞা (L06-এর $\exists c, n_0$-ভিত্তিক) সীমার অস্তিত্বের উপর নির্ভর করে না — তাই এই দুটো তখনও প্রযোজ্য হতে পারে, শুধু সীমা-ট্রিক ব্যবহার করে সহজে চেক করা যাবে না, মূল সংজ্ঞা দিয়েই সরাসরি প্রমাণ করতে হবে। এই কারণেই সীমা-পদ্ধতিকে "একটি সুবিধাজনক শর্টকাট" হিসেবে দেখা উচিত, প্রতিস্থাপনকারী সংজ্ঞা হিসেবে নয়।

অনুশীলন

চিন্তা করুন: $f(n) = n \log n$ এবং $g(n) = n^2$ হলে $\lim_{n\to\infty} f(n)/g(n)$ কী হবে বলে আপনার ধারণা, এবং এটি $o$, $\Theta$, নাকি $\omega$ নির্দেশ করে?

$\frac{n\log n}{n^2} = \frac{\log n}{n}$, যা $n\to\infty$ হলে $0$-এর দিকে যায় (কারণ $\log n$, $n$-এর চেয়ে অনেক ধীরে বাড়ে — L05-এর গ্রোথ ক্রম মনে করুন)। তাই সীমা $=0$, অর্থাৎ $n\log n = o(n^2)$।
পরীক্ষা করুন: উপরের কোড সেলে f1-কে def f1(n): return n * math.log2(n) দিয়ে বদলে (এবং ফাইলের শুরুতে import math যোগ করে) চালিয়ে আপনার অনুমান যাচাই করুন।

আউটপুটে প্রথম কলামের মান ক্রমাগত ছোট হতে থাকবে ($n=10$-এ প্রায় $0.033$, $n=1{,}000{,}000$-এ প্রায় $0.00002$) — অর্থাৎ $0$-এর দিকে অভিসৃত হচ্ছে, ঠিক যেমন হাতে-করা হিসাবে পাওয়া গিয়েছিল। এটি নিশ্চিত করে $n\log n = o(n^2)$।

এই পাঠে যা শিখবেন

১ · O বনাম o — অ-কঠোর বনাম কঠোর

২ · কোড সেল — অনুপাত গণনা করে সম্পর্ক শনাক্ত করা

ভাবনার প্রশ্ন

অনুশীলন

আরও পড়ুন · ABCL TECH-এ আপনার পরবর্তী পদক্ষেপ