लेक्चर नोट्स: ग्रोथ ऑफ फंक्शन और एसिम्प्टोटिक नोटेशन

प्रारंभिक बातें

• फॉलो करें हमारे फेसबुक पेज को और सब्सक्राइब करें यूट्यूब चैनल को टेकनिकल सब्जेक्ट और टेक न्यूज के वीडियो सबसे पहले पाने के लिए।
• आज का विषय: ग्रोथ ऑफ फंक्शन और एसिम्प्टोटिक नोटेशन।

ग्रोथ ऑफ फंक्शन

• विभिन्न एल्गोरिदम का टाइम कॉम्प्लेक्सिटी।
• कुछ महत्वपूर्ण टाइम कॉम्प्लेक्सिटी:
  • 1
  • n
  • n log n
  • n²
  • n³
  • 2ⁿ, 3ⁿ, nⁿ
• सबसे छोटे फंक्शन की ग्रोथ: 1, उसके बाद log n, √n, n, n log n, n², n³, आदि।

एसिम्प्टोटिक नोटेशन

• एसिम्प्टोटिक नोटेशन का उपयोग टाइम और स्पेस कॉम्प्लेक्सिटी को दर्शाने के लिए किया जाता है।
• प्रमुख नोटेशन:
  • बिग O (Upper Bound)
  • बिग ओमेगा (Lower Bound)
  • थीटा (Tight Bound)

बिग O (O) नोटेशन

• एक फंक्शन f(n) के लिए, f(n) को O(g(n)) कहा जाता है यदि:
  • पॉजिटिव कॉन्स्टेंट C और n₀ ऐसे हों कि:
    • f(n) ≤ C * g(n) (जब n ≥ n₀ हो)।
• उदाहरण:
  • f(n) = 3n + 2, g(n) = n
  • C की वैल्यू 4 रखकर, n₀ की वैल्यू 2।

बिग ओमेगा (Ω) नोटेशन

• एक फंक्शन f(n) के लिए, f(n) को Ω(g(n)) कहा जाता है यदि:
  • पॉजिटिव कॉन्स्टेंट C और n₀ ऐसे हों कि:
    • f(n) ≥ C * g(n) (जब n ≥ n₀ हो)।
• उदाहरण:
  • f(n) = 3n + 2, g(n) = n
  • C की वैल्यू 3 रखकर, n₀ की वैल्यू 1।

थीटा (Θ) नोटेशन

• एक फंक्शन f(n) के लिए, f(n) को Θ(g(n)) कहा जाता है यदि:
  • पॉजिटिव कॉन्स्टेंट C₁, C₂ और n₀ ऐसे हों कि:
    • C₁ * g(n) ≤ f(n) ≤ C₂ * g(n) (जब n ≥ n₀ हो)।
• उदाहरण:
  • f(n) = 3n + 2, g(n) = n
  • C₁ की वैल्यू 3 और C₂ की वैल्यू 4।

निष्कर्ष

• ग्रोथ ऑफ फंक्शन और एसिम्प्टोटिक नोटेशन की सही समझ आवश्यक है।
• इन नोटेशनों का सही उपयोग समय और स्थान की जटिलता को व्यक्त करने में मदद करता है।
• अगली कक्षा में हम और भी गहराई में जाएंगे।

---

नोट: यह नोट्स आपके अध्ययन में सहायक साबित हो सकते हैं।