পাঠ ৩৭ · ৪৪-এর মধ্যে · মডিউল ৮
Home / Courses / Discrete Mathematics / Big-O নোটেশন

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

Big-O notation — upper bounds
৯ মিনিট পড়া মধ্যম · Intermediate Python কোডসহ সম্পূর্ণ বাংলায়

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

  • Big-O-এর আনুষ্ঠানিক ($c, n_0$-ভিত্তিক) সংজ্ঞা
  • $3n^2+5n+2 = O(n^2)$-এর একটি সম্পূর্ণ, হাতে-কলমে যাচাইযোগ্য প্রমাণ
  • নিম্ন-ক্রমের টার্ম ও ধ্রুবক গুণক বাদ দেওয়ার সরলীকরণ নিয়মের যুক্তি
  • Big-O সম্পর্কে সবচেয়ে সাধারণ ভুল ধারণা ও কেন সেটি ভুল

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

Big-OBig-O Notationএকটি ফাংশনের বৃদ্ধির হারের উপরের সীমা (upper bound) বর্ণনা করার নোটেশন — বলে "এই ফাংশন এর চেয়ে দ্রুত বাড়ে না"। একটি ফাংশনের আপার বাউন্ড বর্ণনা করে —

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

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

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

অর্থাৎ — একটি নির্দিষ্ট বিন্দুর ($n_0$) পর থেকে, $f(n)$ সবসময় $g(n)$-এর একটি ধ্রুবক গুণিতকের চেয়ে ছোট বা সমান থাকে। Big-O শুধু upper bound — "সর্বোচ্চ এত দ্রুত", কম দ্রুত হলেও চলবে।

২ · Worked প্রমাণ — $3n^2+5n+2 = O(n^2)$

দাবি: $3n^2 + 5n + 2 = O(n^2)$। আমরা $c=10$ এবং $n_0=1$ বেছে নেব এবং দেখাব সব $n \geq 1$-এর জন্য $3n^2+5n+2 \leq 10n^2$।

ইনইকুয়ালিটি চেইন

$n \geq 1$ হলে, $n \leq n^2$ এবং $1 \leq n^2$ (উভয়ই সহজেই যাচাইযোগ্য: $n=1$-এ $1 \leq 1$; $n$ বাড়লে $n^2$ আরও দ্রুত বাড়ে)। তাই —

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

(এখানে $5n \leq 5n^2$ কারণ $n \leq n^2$, এবং $2 \leq 2n^2$ কারণ $1 \leq n^2$।) তাই $c=10, n_0=1$ দিয়ে সংজ্ঞা সন্তুষ্ট হয় — $3n^2+5n+2 = O(n^2)$ প্রমাণিত।

যাচাই — $n=1$: $3+5+2=10 \leq 10(1)=10$ ✓ (সমান, তাই ঠিক সীমানায়)।   $n=2$: $12+10+2=24 \leq 10(4)=40$ ✓ (এখানে যথেষ্ট মার্জিন আছে)।

৩ · সরলীকরণ নিয়ম

Big-O লেখার সময় সাধারণত দুটি সরলীকরণ করা হয়, উভয়ই উপরের সংজ্ঞা থেকে ন্যায্য —

  • নিম্ন-ক্রমের টার্ম বাদ দাও: $3n^2+5n+2$-কে সরাসরি $O(n^2)$ লেখা যায় — কারণ যথেষ্ট বড় $n$-এ, $n^2$ টার্মই প্রাধান্য পায়, বাকি টার্মগুলো একটি ধ্রুবক $c$ দিয়ে "শোষণ" করে নেওয়া যায় (যেমন উপরে দেখানো হলো)।
  • ধ্রুবক গুণক বাদ দাও: $O(5n^2)$ এবং $O(n^2)$ একই জিনিস — কারণ $c$ নিজেই একটি স্বাধীন ধ্রুবক, তাই $5n^2 \leq c \cdot n^2$ শুধু $c=5$ (বা তার বেশি) বেছে নিলেই সন্তুষ্ট হয়।
Python
ok = True
for n in range(1, 101):
    lhs = 3*n**2 + 5*n + 2
    rhs = 10*n**2
    if lhs > rhs:
        ok = False

print("n=1 থেকে 100 পর্যন্ত সব n-এ 3n^2+5n+2 <= 10n^2 ?", ok)
print("n=1:", 3*1**2 + 5*1 + 2, "<=", 10*1**2)
print("n=2:", 3*2**2 + 5*2 + 2, "<=", 10*2**2)

    


    
৪ · সবচেয়ে সাধারণ ভুল ধারণা

    

      সতর্কতা
      

        $O(n^2)$ মানে এই নয় যে অ্যালগরিদমটি "ঠিক $n^2$ ধাপ" নেয় — এটি শুধু বলে "এই অ্যালগরিদম
        $n^2$-এর চেয়ে দ্রুত বাড়ে না"। তাই একটি $O(1)$ (কনস্ট্যান্ট-টাইম) অ্যালগরিদম টেকনিক্যালি $O(n^2)$-ও
        বটে, এবং $O(n \log n)$-ও, এবং $O(2^n)$-ও — কারণ এই সবগুলোই বৈধ (যদিও অকার্যকরী) আপার বাউন্ড। Big-O কখনো একটি
        টাইট বাউন্ড দেওয়ার প্রতিশ্রুতি দেয় না — শুধু একটি বৈধ উপরের সীমা দেয়। টাইট বাউন্ড (উপরে ও নিচে
        উভয়ই একসাথে) বর্ণনা করার নোটেশন — Big-Theta ($\Theta$) — L38-এ দেখব।
      

    


    

      মূল কথা · Key takeaway
      

        Big-O একটি প্রতিশ্রুতি — "এই অ্যালগরিদম কখনোই এই সীমার চেয়ে খারাপ আচরণ করবে না"। এটি একটি নিশ্চয়তা (guarantee),
        একটি বর্ণনা নয় (description)। এই পার্থক্যটি বুঝলে পরবর্তী পাঠে Big-Omega ও Big-Theta-র প্রয়োজনীয়তা সহজেই
        বোঝা যাবে।
      

    


  


  

    
    
  


  

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

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


    

      
        প্র ০১
        প্রমাণে আমরা $c=10, n_0=1$ বেছে নিয়েছি। এটি কি একমাত্র বৈধ পছন্দ, নাকি অন্য $(c, n_0)$ জোড়াও কাজ করতে পারত?
      
      

        

          একমাত্র নয় — Big-O সংজ্ঞায় $(c, n_0)$ অনন্য (unique) হতে হয় না, শুধু কোনো একটি বৈধ জোড়া থাকতে
          হবে। যেমন $c=11, n_0=1$ও কাজ করবে (আরও বেশি মার্জিন দিয়ে)। এমনকি $n_0=2$ বেছে $c$ একটু ছোট
          করলেও (যেমন $c=8$) সম্ভবত কাজ করবে, কারণ বড় $n$-এ নিম্ন-ক্রমের টার্মের আপেক্ষিক প্রভাব কমে যায়।
        

        

          মূল কথা: একটি Big-O দাবি প্রমাণ করতে আপনাকে কমপক্ষে একটি বৈধ $(c, n_0)$ জোড়া দেখাতে হবে — "সবচেয়ে
          ছোট" বা "সেরা" জোড়া খোঁজার কোনো প্রয়োজন নেই। এই নমনীয়তাই Big-O প্রমাণকে ব্যবহারিকভাবে সহজ করে তোলে।
        

      

    


    

      
        প্র ০২
        $n^2 = O(n^3)$ কি সত্যি? এটি কি $n^2$-কে "ভুলভাবে" বড় দেখানো নয়?
      
      

        

          হ্যাঁ, $n^2 = O(n^3)$ সত্যিই সঠিক — $c=1, n_0=1$ দিয়ে: সব $n \geq 1$-এর জন্য $n^2 \leq 1 \cdot n^3$ (কারণ
          $n \geq 1 \Rightarrow n^3 = n^2 \cdot n \geq n^2 \cdot 1 = n^2$)। এটি "ভুল" নয় — এটি Big-O-এর সংজ্ঞারই
          স্বাভাবিক ফলাফল, যেমন প্র ০১-এর উত্তরে উল্লেখ করা হয়েছে যে Big-O একটি আপার বাউন্ড, টাইট বাউন্ড
          নয়।
        

        

          বাস্তবে যখন আমরা বলি "এই অ্যালগরিদম $O(n^2)$", আমরা সাধারণত বোঝাতে চাই এটিই সবচেয়ে টাইট (tightest)
          বর্ণনা যা আমরা প্রমাণ করতে পারি — যদিও আনুষ্ঠানিকভাবে $O(n^3)$, $O(n^4)$ ইত্যাদিও সমানভাবে "সত্য"। এই কারণেই
          বাস্তব ব্যবহারে সবসময় সবচেয়ে টাইট বাউন্ড উল্লেখ করার একটি অলিখিত রীতি (convention) আছে, এবং L38-এ Big-Theta
          ঠিক এই "টাইট বাউন্ড"-এর জন্য একটি আনুষ্ঠানিক নোটেশন দেয়।
        

      

    


    

      
        প্র ০৩
        যদি একটি অ্যালগরিদমের প্রকৃত ধাপ-সংখ্যা $f(n) = 100$ (একটি ধ্রুবক, $n$-এর উপর নির্ভর করে না) হয়, তাহলে এর সঠিকতম Big-O কী?
      
      

        

          এটি $O(1)$ — অর্থাৎ constant time। যেহেতু $f(n)=100$ কখনোই $n$-এর সাথে বাড়ে না, একটি ধ্রুবক $g(n)=1$-এর
          সাথে $c=100, n_0=1$ বেছে নিলেই $f(n) \leq c \cdot 1$ সন্তুষ্ট হয় — সংজ্ঞা অনুযায়ী এটি বৈধ।
        

        

          তবে (প্র ০১-এর মতো যুক্তিতে) $f(n)=100$ টেকনিক্যালি $O(n)$, $O(n^2)$, $O(\log n)$-ও বটে (যেকোনো ক্রমবর্ধমান
          ফাংশনের জন্য) — কিন্তু $O(1)$ হলো সবচেয়ে টাইট ও সবচেয়ে তথ্যবহুল বর্ণনা, তাই এটিই ব্যবহার করা উচিত।
        

      

    

  


  

    
 অনুশীলন

    
    
      
  1. 
        প্রমাণ করুন: $5n + 3 = O(n)$ প্রমাণ করুন একটি নির্দিষ্ট $(c, n_0)$ জোড়া বেছে নিয়ে (উপরের পদ্ধতি অনুসরণ করুন)।
        
    
          
          
    
            
    
              $c=8, n_0=1$ বেছে নিন। $n \geq 1$-এর জন্য: $5n+3 \leq 5n+3n=8n$ (কারণ $3 \leq 3n$ যখন $n \geq 1$)। তাই
              সব $n \geq 1$-এর জন্য $5n+3 \leq 8n$ — সংজ্ঞা সন্তুষ্ট, $5n+3=O(n)$ প্রমাণিত। (ছোট $c$-ও কাজ করতে পারে,
              যেমন $c=6, n_0=2$: $n \geq 2$-এ $5n+3 \leq 6n \Leftrightarrow 3 \leq n$, যা সত্য।)
            
    
          
    
        
    
      
    2. 
      
  2. 
        কোড পরীক্ষা করুন: উপরের কোড সেলে 10*n**2-এর বদলে 8*n**2 ব্যবহার করে দেখুন সব $n=1..100$-এ ইনইকুয়ালিটি এখনো ধরে কি না ($c=8$ কি যথেষ্ট?)।
        
    
          
          
    
            
    
              $n=1$-এ পরীক্ষা করুন: $3(1)+5(1)+2=10$, কিন্তু $8(1)^2=8$। যেহেতু $10 > 8$, $c=8$ $n_0=1$-এ কাজ করে না
              — কোড ok=False দেখাবে (অন্তত $n=1$-এর জন্য ব্যর্থ হবে)। তবে বড় $n$-এ (যেমন $n \geq 2$)
              $c=8$ যথেষ্ট হতে পারে — এটি দেখায় কীভাবে $c$ ও $n_0$ একে অপরের সাথে ট্রেড-অফ সম্পর্কে জড়িত: ছোট $c$
              হলে বড় $n_0$ প্রয়োজন হতে পারে।
            
    
          
    
        
    
      
    3. 
    

  


  

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

    
  







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





  
    
 আগের পাঠ

    
অ্যালগরিদম বিশ্লেষণ কেন জরুরি