পাঠ ৩৮ · ৪৪-এর মধ্যে · মডিউল ৮
Home / Courses / Discrete Mathematics / Big-Ω ও Big-Θ

Big-Ω ও Big-Θ নোটেশন

Big-Omega & Big-Theta notation
৮ মিনিট পড়া মধ্যম · Intermediate Python কোডসহ সম্পূর্ণ বাংলায়

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

  • Big-Omega ($\Omega$)-এর আনুষ্ঠানিক সংজ্ঞা — লোয়ার বাউন্ড
  • Big-Theta ($\Theta$)-এর আনুষ্ঠানিক সংজ্ঞা — টাইট বাউন্ড (O এবং Ω একসাথে)
  • $3n^2+5n+2=\Theta(n^2)$-এর একটি সম্পূর্ণ, উভয়দিকের worked প্রমাণ
  • O/Ω/Θ-কে ≤/≥/= এর সাথে তুলনা করে সহজে মনে রাখার পদ্ধতি

১ · Big-Omega ($\Omega$) — লোয়ার বাউন্ড

L37-এ Big-O দেখিয়েছিল একটি ফাংশন সর্বোচ্চ কত দ্রুত বাড়তে পারে। কিন্তু কখনো কখনো আমরা উল্টো প্রশ্ন করতে চাই — একটি ফাংশন সর্বনিম্ন কত দ্রুত বাড়ে তার একটি গ্যারান্টি। এই কাজ করে Big-Omega ($\Omega$)Big-Omegaএকটি ফাংশনের বৃদ্ধির হারের নিচের সীমা (lower bound) বর্ণনা করার নোটেশন — বলে "এই ফাংশন এর চেয়ে ধীরে বাড়ে না"। —

আনুষ্ঠানিক সংজ্ঞা

$f(n) = \Omega(g(n))$ যদি এবং কেবল যদি ধনাত্মক ধ্রুবক $c$ এবং $n_0$ থাকে এমন যে —

$$f(n) \geq c \cdot g(n) \quad \text{সব } n \geq n_0 \text{-এর জন্য}$$

লক্ষ্য করুন — এটি Big-O-এর সংজ্ঞার ঠিক আয়না-প্রতিবিম্ব (mirror image), শুধু $\leq$-এর বদলে $\geq$।

২ · Big-Theta ($\Theta$) — টাইট বাউন্ড

যখন একটি ফাংশনের উপরের ও নিচের সীমা একই growth rate-এ মিলে যায়, তখন আমরা বলতে পারি সেই ফাংশনের growth rate ঠিক ততটাই — এই ধারণাটি ধরে Big-Theta ($\Theta$)Big-Thetaএকটি ফাংশনের বৃদ্ধির হারের টাইট (tight) বাউন্ড — একই সাথে upper ও lower bound, অর্থাৎ ফাংশনটি ঠিক এই হারে বাড়ে, ধ্রুবক গুণক বাদে। —

আনুষ্ঠানিক সংজ্ঞা

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

অর্থাৎ $f$ এবং $g$-এর growth rate ধ্রুবক গুণক পর্যন্ত হুবহু সমান — $f$ কখনো $g$-এর চেয়ে দ্রুতও বাড়ে না, ধীরেও বাড়ে না।

৩ · Worked উদাহরণ — $3n^2+5n+2=\Theta(n^2)$

L37-এ আমরা ইতিমধ্যে দেখিয়েছি উপরের বাউন্ড। এখন নিচের বাউন্ডও দেখানো দরকার।

দুই দিকের প্রমাণ

উপরের বাউন্ড (L37 থেকে): $c=10, n_0=1$ দিয়ে, সব $n \geq 1$-এ $3n^2+5n+2 \leq 10n^2$।

নিচের বাউন্ড (নতুন): $c=3, n_0=1$ বেছে নিন। সব $n \geq 1$-এর জন্য $5n+2 > 0$ (স্পষ্টতই, যেহেতু $n \geq 1$), তাই —

$$3n^2 + 5n + 2 \geq 3n^2 \quad \text{(তুচ্ছভাবে সত্য, কারণ } 5n+2 > 0 \text{)}$$

এই দুই বাউন্ড একসাথে দেখায় সব $n \geq 1$-এর জন্য —

$$3n^2 \leq 3n^2+5n+2 \leq 10n^2$$

অর্থাৎ $3n^2+5n+2$ সবসময় $n^2$-এর একটি ধ্রুবক গুণিতকের মধ্যে "স্যান্ডউইচ" হয়ে থাকে — এটিই $3n^2+5n+2=\Theta(n^2)$-এর প্রমাণ।

Python
ok = True
for n in range(1, 51):
    f = 3*n**2 + 5*n + 2
    upper = 10*n**2  # c=10 (Big-O, L37 থেকে)
    lower = 3*n**2   # c=3 (Big-Omega, এই পাঠে নতুন)
    if not (lower <= f <= upper):
        ok = False

print("n=1 থেকে 50 পর্যন্ত 3n^2 <= 3n^2+5n+2 <= 10n^2 ?", ok)
print("n=1: নিচের বাউন্ড", 3*1**2, "<=", 3*1**2+5*1+2, "<= উপরের বাউন্ড", 10*1**2)
print("n=50: নিচের বাউন্ড", 3*50**2, "<=", 3*50**2+5*50+2, "<= উপরের বাউন্ড", 10*50**2)
print()
print("দুই বাউন্ডই ধরে -> 3n^2+5n+2 = Theta(n^2) নিশ্চিত")

    


    
৪ · মনে রাখার সহজ ছক

    

      O, Ω, Θ — এই তিনটি নোটেশনকে সংখ্যা তুলনার সাথে মিলিয়ে মনে রাখা সহজ —
    


    

      
Big-O ~ "≤"
$f$ সর্বোচ্চ $g$-এর সমান হারে বাড়ে (upper bound)

      
Big-Ω ~ "≥"
$f$ সর্বনিম্ন $g$-এর সমান হারে বাড়ে (lower bound)

      
Big-Θ ~ "="
$f$ ঠিক $g$-এর সমান হারে বাড়ে (tight bound — উভয় দিক)

    


    

      বাস্তব চর্চায় প্রায়ই মানুষ ঢিলেঢালাভাবে "Big-O" বলেন যখন প্রকৃতপক্ষে "Big-Theta" বোঝাতে চান (যেমন "merge sort
      $O(n \log n)$" — বাস্তবে এটি $\Theta(n \log n)$-ও, কারণ merge sort সবসময় ঠিক এই হারেই চলে, ভালো বা খারাপ কেসেও)।
      কিন্তু আনুষ্ঠানিকভাবে দুটো ভিন্ন জিনিস — যেখানে টাইট বাউন্ড জানা যায়, সেখানে $\Theta$ ব্যবহার করাই বেশি
      সুনির্দিষ্ট।
    


    

      মূল কথা · Key takeaway
      

        O, Ω, Θ একসাথে অ্যালগরিদমের growth rate বর্ণনা করার একটি সম্পূর্ণ গাণিতিক ভাষা তৈরি করে — উপরের সীমা, নিচের
        সীমা এবং টাইট বাউন্ড। L39-এ আমরা এই ভাষা ব্যবহার করে সবচেয়ে সাধারণ জটিলতা ক্লাসগুলো ($O(1)$ থেকে $O(2^n)$
        পর্যন্ত) সাজিয়ে দেখব।
      

    


  


  

    
    
  


  

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

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


    

      
        প্র ০১
        যদি একটি অ্যালগরিদমের জন্য $f(n)=O(n^2)$ প্রমাণিত থাকে কিন্তু $f(n)=\Omega(n^2)$ প্রমাণিত না থাকে, তাহলে কি আমরা বলতে পারি $f(n)=\Theta(n^2)$?
      
      

        

          না। $\Theta$-এর সংজ্ঞা অনুযায়ী উভয় দিকই — $O$ এবং $\Omega$ — আলাদাভাবে প্রমাণ করতে হবে।
          শুধু উপরের বাউন্ড জানা থাকলে ফাংশনটি আসলে তার চেয়ে অনেক ধীরেও বাড়তে পারে (যেমন $f(n)=O(1)$ হলেও এটি
          $O(n^2)$-এর সংজ্ঞা সন্তুষ্ট করে, কিন্তু $\Omega(n^2)$ নয়)।
        

        

          এই কারণেই L37-এ শুধু Big-O দেখানো এবং এই পাঠে (L38) আলাদাভাবে Big-Omega দেখানো দুটোই প্রয়োজন ছিল —
          $3n^2+5n+2$-এর ক্ষেত্রে দুটোই সত্য বলে আমরা $\Theta(n^2)$ দাবি করতে পেরেছি, কিন্তু এটি সবসময় স্বয়ংক্রিয়ভাবে
          হয় না।
        

      

    


    

      
        প্র ০২
        Quicksort-এর worst case $\Theta(n^2)$ কিন্তু average case $\Theta(n \log n)$ (L40-এ বিস্তারিত)। এই দুটো কি একে অপরের সাথে সাংঘর্ষিক?
      
      

        

          না, সাংঘর্ষিক নয় — কারণ এই দুটো ভিন্ন প্রেক্ষাপটে (context) বলা দাবি। "$\Theta(n^2)$ worst case"
          মানে সবচেয়ে খারাপ ইনপুটে (যেমন ইতিমধ্যে সাজানো একটি অ্যারে, খারাপ pivot বাছাইয়ের সাথে) ঠিক $n^2$-এর হারে
          বাড়ে। "$\Theta(n \log n)$ average case" মানে র‍্যান্ডম/সাধারণ ইনপুটে গড়ে $n \log n$-এর হারে বাড়ে।
        

        

          একই অ্যালগরিদমের বিভিন্ন ইনপুট-শ্রেণীর (input class) জন্য বিভিন্ন Θ-বাউন্ড থাকতে পারে — এটি কোনো
          অসামঞ্জস্যতা নয়, বরং একটি গুরুত্বপূর্ণ সূক্ষ্মতা যা L40-এ (সেরা/গড়/সবচেয়ে খারাপ কেস বিশ্লেষণ) বিস্তারিত
          কভার হবে।
        

      

    


    

      
        প্র ০৩
        $O(g(n))$ এবং $\Omega(g(n))$-এর সংজ্ঞায় $(c, n_0)$ কি একই মান হতে হবে?
      
      

        

          না, একদমই না। উপরের worked উদাহরণেই দেখা গেছে — Big-O-তে আমরা $c=10$ ব্যবহার করেছি, কিন্তু
          Big-Omega-তে $c=3$। এই দুটো সম্পূর্ণ স্বাধীন প্রমাণ, প্রতিটির নিজস্ব $(c, n_0)$ বেছে নেওয়ার স্বাধীনতা আছে।
        

        

          একমাত্র শর্ত হলো: Big-O-এর $c$ যথেষ্ট বড় হতে হবে যাতে $f(n) \leq c \cdot g(n)$ ধরে (উপরের দিকে
          মার্জিন), আর Big-Omega-এর $c$ যথেষ্ট ছোট হতে হবে যাতে $f(n) \geq c \cdot g(n)$ ধরে (নিচের দিকে
          মার্জিন)। এই দুই $c$ প্রায় সবসময়ই আলাদা হবে, এবং সেটাই স্বাভাবিক।
        

      

    

  


  

    
 অনুশীলন

    
    
      
  1. 
        প্রমাণ করুন: $n^2 + 100 = \Omega(n^2)$ প্রমাণ করুন একটি নির্দিষ্ট $(c, n_0)$ জোড়া বেছে নিয়ে।
        
    
          
          
    
            
    
              $c=1, n_0=1$ বেছে নিন। সব $n \geq 1$-এর জন্য $n^2+100 \geq n^2 = 1 \cdot n^2$ (তুচ্ছভাবে সত্য, কারণ
              $100 > 0$)। তাই সংজ্ঞা সন্তুষ্ট, $n^2+100=\Omega(n^2)$ প্রমাণিত। প্রকৃতপক্ষে এটি $O(n^2)$-ও (একই যুক্তিতে
              যেমন $3n^2+5n+2$-এর ক্ষেত্রে করা হয়েছে), তাই $n^2+100=\Theta(n^2)$।
            
    
          
    
        
    
      
    2. 
      
  2. 
        কোড পরীক্ষা করুন: উপরের কোড সেলে lower = 3*n**2-এর বদলে lower = 4*n**2 বসিয়ে দেখুন সব $n=1..50$-এ ইনইকুয়ালিটি এখনো ধরে কি না, এবং কেন।
        
    
          
          
    
            
    
              $c=4$-এ, $n=1$-এ পরীক্ষা: $4(1)^2=4$, কিন্তু $3(1)^2+5(1)+2=10$। যেহেতু $10 \geq 4$, এই নির্দিষ্ট বিন্দুতে
              এখনো ঠিক আছে! কিন্তু বড় $n$-এ (যেমন $n=50$): $4(50)^2=10000$, আর $3(50)^2+5(50)+2=7752$। এখানে
              $7752 < 10000$ — ইনইকুয়ালিটি ভেঙে যায়। তাই $c=4$ সব $n$-এ কাজ করে না — এটি দেখায় $c$ বাছাই যত্নসহকারে
              করা জরুরি, ছোট $n$-এ কাজ করলেই যথেষ্ট নয়।
            
    
          
    
        
    
      
    3. 
    

  


  

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

    
  







  
  
     এই পাঠে ভুল পেয়েছেন? জানান
  





  
    
 আগের পাঠ

    
Big-O নোটেশন — আপার বাউন্ড