Big-O, Big-Omega ও Big-Theta

১ · Big-O — আনুষ্ঠানিক সংজ্ঞা

$$f(n) = O(g(n)) \iff \exists\, c > 0,\ n_0 > 0 \text{ এমন যে } 0 \le f(n) \le c \cdot g(n) \text{ সব } n \ge n_0\text{-এর জন্য}$$

এই সংজ্ঞার প্রতিটি অংশ গুরুত্বপূর্ণ। $\exists c, n_0$ মানে — এমন অন্তত একটি জোড়া $(c, n_0)$ পাওয়া গেলেই দাবিটি সত্য, একাধিক জোড়া থাকতে পারে এবং তাদের মধ্যে "সবচেয়ে ভালো" কোনোটি খোঁজার দরকার নেই। $n \ge n_0$ মানে — ছোট $n$-এ (যেমন $n < n_0$) ইনইকুয়ালিটি ভাঙলেও কোনো সমস্যা নেই; শুধু $n_0$-এর পর থেকে সবসময় সত্য থাকতে হবে। এটিই আসলে L05-এ আমরা কম্পিউটেশনালি যা খুঁজেছিলাম তার আনুষ্ঠানিক রূপ — "স্থায়ী ক্রসওভার পয়েন্ট" হলো ঠিক এই $n_0$।

২ · Big-Omega ও Big-Theta

$\Omega$ (নিচের সীমা) এবং $\Theta$ (টাইট বাউন্ড) একইভাবে সংজ্ঞায়িত, শুধু ইনইকুয়ালিটির দিক পাল্টায়:

$$f(n) = \Omega(g(n)) \iff \exists\, c > 0,\ n_0 > 0 \text{ এমন যে } 0 \le c \cdot g(n) \le f(n) \text{ সব } n \ge n_0\text{-এর জন্য}$$

$$f(n) = \Theta(g(n)) \iff \exists\, c_1, c_2 > 0,\ n_0 > 0 \text{ এমন যে } c_1 \cdot g(n) \le f(n) \le c_2 \cdot g(n) \text{ সব } n \ge n_0\text{-এর জন্য}$$

$\Omega(g(n))$ মানে $f(n)$ কমপক্ষে $g(n)$-এর সমান দ্রুত বাড়ে (একটি ধ্রুবক গুণিতক পর্যন্ত) — এটি $O$-এর আয়না-প্রতিবিম্ব। আর $\Theta(g(n))$ মানে $f(n)$ ঠিক $g(n)$-এর সমান গ্রোথ ক্লাসে আটকে আছে, উপরে ও নিচে দুই দিক থেকেই। একটি গুরুত্বপূর্ণ সমতুল্যতা মনে রাখার মতো:

$$f(n) = \Theta(g(n)) \iff f(n) = O(g(n)) \text{ এবং } f(n) = \Omega(g(n))$$

৩ · কোড সেল — একটি বৈধ (c, n₀) কম্পিউটেশনালি খুঁজে বের করা

নিচের কোড সেলে দুটি কাজ করা হয়েছে। প্রথমত, $f(n) = 3n^2 + 5n + 2$ যে $O(n^2)$ তার একটি বৈধ $(c, n_0)$ জোড়া কম্পিউটেশনালি খোঁজা হয়েছে ($c=1$ থেকে শুরু করে ছোট থেকে বড় দিকে পরীক্ষা করে)। দ্বিতীয়ত, একটি ভুল দাবি — $f(n) = n^2$ হলো $O(n)$ — পরীক্ষা করে দেখানো হয়েছে $c=10$-এর মতো "প্রথম দেখায় যুক্তিসঙ্গত" একটি ধ্রুবকও ছোট $n$-এ কাজ করলেও বড় $n$-এ স্থায়ীভাবে ব্যর্থ হয় — কারণ $n^2$ আসলে $O(n)$ শ্রেণির নয়।

def f_quad(n):
    return 3 * n**2 + 5 * n + 2

def g_quad(n):
    return n ** 2

def check_bound(f, g, c, n0, test_range):
    """f(n) <= c*g(n) সব n in test_range (n >= n0) -তে সত্য কিনা যাচাই করে;
    ব্যর্থ হলে প্রথম ব্যর্থ n সহ রিপোর্ট করে।"""
    failures = [n for n in test_range if n >= n0 and f(n) > c * g(n)]
    return (len(failures) == 0), (failures[0] if failures else None)

test_ns = range(1, 1001)

# --- ধাপ ১: সঠিক দাবি -- f(n)=3n^2+5n+2 হলো O(n^2); n0=1 ধরে বৈধ c খোঁজা ---
n0 = 1
best_c = None
for c_candidate in range(1, 21):
    ok, _ = check_bound(f_quad, g_quad, c_candidate, n0, test_ns)
    if ok:
        best_c = c_candidate
        break

print("claim: f(n) = 3n^2 + 5n + 2 হলো O(n^2)")
print(f"কম্পিউটেশনালি খুঁজে পাওয়া বৈধ (c, n0): (c={best_c}, n0={n0})")
ok, _ = check_bound(f_quad, g_quad, best_c, n0, test_ns)
print(f"n=1 থেকে 1000 পর্যন্ত সব n-এ f(n) <= {best_c}*g(n) সত্য? {ok}")

# --- ধাপ ২: ভুল দাবি -- f(n)=n^2 হলো O(n) দাবি করলে কী হয় ---
def f_sq(n):
    return n ** 2

def g_lin(n):
    return n

wrong_c = 10
ok2, fail_n2 = check_bound(f_sq, g_lin, wrong_c, 1, test_ns)
print(f"\nভুল claim: f(n) = n^2 হলো O(n), c={wrong_c} দিয়ে চেষ্টা:")
print(f"n=1 থেকে 1000 পর্যন্ত সব n-এ f(n) <= {wrong_c}*g(n) সত্য? {ok2}")
print(f"প্রথম যে n-এ ব্যর্থ হয়: n = {fail_n2}  "
      f"(f({fail_n2})={f_sq(fail_n2)}, {wrong_c}*g({fail_n2})={wrong_c * g_lin(fail_n2)})")

still_failing = all(f_sq(n) > wrong_c * g_lin(n) for n in range(fail_n2, fail_n2 + 20))
print(f"n={fail_n2} থেকে {fail_n2 + 19} পর্যন্ত পরের ২০টি n-ও কি ব্যর্থ থাকে? {still_failing}")