PGDCA, BCA, B-Tech, MCA, M-Tech, B.Sc computer science राजस्थान सूचना सहायक व कंप्यूटर शिक्षक विशेष नोट्स: इस अध्याय में हम Asymptotic Notations: Big-O, Big-Omega (Ω), Big-Theta (Θ) (एसिम्प्टोटिक नोटेशन्स: Big-O (उच्चतम सीमा), Big-Omega, Big-Theta) की संपूर्ण थ्योरी, मुख्य तकनीकी बिंदु, तुलनात्मक तालिका और विगत परीक्षाओं के पैटर्न पर आधारित 20 अति-महत्वपूर्ण बहुविकल्पीय प्रश्न (MCQs) विस्तृत हिंदी व अंग्रेजी व्याख्या सहित पढ़ेंगे।
Overview: Asymptotic notations mathematically classify algorithm growth rates as input size approaches infinity: Big-O gives an upper bound, Big-Omega gives a lower bound, and Big-Theta gives a tight bound.
अध्याय सार: एसिम्प्टोटिक नोटेशन्स अनंत की ओर बढ़ते इनपुट आकार के लिए एल्गोरिदम की वृद्धि दर को परिभाषित करते हैं: Big-O उच्चतम सीमा (Upper Bound), Big-Omega न्यूनतम सीमा (Lower Bound) और Big-Theta सटीक सीमा (Tight Bound) बताता है।
Asymptotic Notations: Big-O, Big-Omega (Ω), Big-Theta (Θ): Detailed Notes & Architecture (एसिम्प्टोटिक नोटेशन्स: Big-O (उच्चतम सीमा), Big-Omega, Big-Theta)
1. Big-O Notation (O): Asymptotic Upper Bound (Big-O नोटेशन (O): उच्चतम सीमा (Upper Bound))
[EN] Formally, f(n) = O(g(n)) if and only if there exist positive constants c > 0 and threshold n0 ≥ 1 such that 0 ≤ f(n) ≤ c · g(n) for all n ≥ n0. Big-O acts like ≤ on growth rates, capping how fast f(n) can grow. Notice a crucial subtlety: mathematically 5n + 7 = O(n) AND 5n + 7 = O(n^2) are both true, though we prefer the tightest O bound; also Big-O is NOT a synonym for Worst-Case—you can state Best-Case Insertion Sort is O(n)!
[HI] गणितीय परिभाषा के अनुसार f(n) = O(g(n)) तब सत्य है जब ऐसे स्थिरांक c > 0 और n0 ≥ 1 मौजूद हों कि सभी n ≥ n0 के लिए 0 ≤ f(n) ≤ c · g(n) हो। Big-O वृद्धि दर के '≤' चिह्न जैसा है। ध्यान दें: 5n + 7 के लिए O(n) और O(n^2) दोनों गणितीय रूप से वैध ऊपरी सीमाएं हैं, और Big-O का अर्थ हमेशा वर्स्ट-केस नहीं होता—बेस्ट-केस समय को भी O(n) में लिखा जा सकता है!
2. Big-Omega (Ω) and Big-Theta (Θ): Lower and Tight Bounds (Big-Omega (Ω) और Big-Theta (Θ): न्यूनतम और सटीक सीमा)
[EN] Big-Omega gives an asymptotic lower bound (≥): f(n) = Ω(g(n)) iff there exist c > 0, n0 such that 0 ≤ c · g(n) ≤ f(n) for all n ≥ n0 (e.g., comparison-based sorting takes Ω(n log n)). Big-Theta gives an exact tight bound (=): f(n) = Θ(g(n)) iff there exist c1, c2 > 0, n0 satisfying 0 ≤ c1 · g(n) ≤ f(n) ≤ c2 · g(n) for all n ≥ n0—which holds if and only if BOTH f(n) = O(g(n)) AND f(n) = Ω(g(n)) simultaneously!
[HI] Big-Omega (Ω) न्यूनतम सीमा (≥) बताता है: 0 ≤ c · g(n) ≤ f(n) (जैसे किसी भी तुलना-आधारित सॉर्टिंग की न्यूनतम सीमा Ω(n log n) है)। Big-Theta (Θ) सटीक बंद सीमा (=) दर्शाता है: c1 · g(n) ≤ f(n) ≤ c2 · g(n)—अर्थात f(n) = Θ(g(n)) तभी सत्य होता है जब f(n) = O(g(n)) और f(n) = Ω(g(n)) दोनों एक साथ लागू हों!
3. Little-o (o) and Little-omega (ω): Strict Non-Tight Bounds (Little-o (o) और Little-omega (ω): कठोर असमानता सीमाएं)
[EN] While Big-O (≤) and Big-Omega (≥) allow bounds to be tight, Little-o (<) and Little-omega (>) enforce strict asymptotic separation via limits. Specifically, f(n) = o(g(n)) iff lim(n → ∞) f(n) / g(n) = 0 (thus 2n = o(n^2) is TRUE, whereas 2n = o(n) is FALSE!). Conversely, f(n) = ω(g(n)) iff lim(n → ∞) f(n) / g(n) = ∞ (e.g., n^2 = ω(n), while n^2 ≠ ω(2n^2)).
[HI] Big-O (≤) और Big-Omega (≥) में समान गति वाली सीमा भी मान्य होती है, परंतु Little-o (<) और Little-omega (>) में सटीक अंतर अनिवार्य है। f(n) = o(g(n)) तभी सत्य होगा जब lim(n → ∞) f(n)/g(n) = 0 हो (अतः 2n = o(n^2) सत्य है पर 2n = o(n) असत्य है)। इसी प्रकार f(n) = ω(g(n)) तब सत्य होता है जब lim(n → ∞) f(n)/g(n) = ∞ आए।
4. Asymptotic Hierarchy, Log Base Independence, and Exponential Pitfalls (वृद्धि दर अनुक्रम, लॉग बेस स्वतंत्रता और घातीय अपवाद)
[EN] The canonical complexity ordering from slowest to fastest growth is: O(1) < O(log log n) < O(log n) < O(√n) < O(n) < O(n log n) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n). By the change-of-base formula log_a(n) = log_b(n) / log_b(a), all constant logarithm bases differ only by a constant factor so log_2(n) = Θ(log_10(n)). Beware exponents: 2^(n+1) = 2 · 2^n = Θ(2^n), whereas 3^n ≠ O(2^n) because (3/2)^n → ∞!
[HI] सबसे धीमी से सबसे तेज़ वृद्धि दर का मानक क्रम: 1 < log log n < log n < √n < n < n log n < n^2 < n^3 < 2^n < n! < n^n है। आधार परिवर्तन सूत्र से सभी लॉग आधार (जैसे log_2(n) और log_10(n)) केवल एक स्थिरांक से भिन्न हैं, अतः दोनों Θ(log n) हैं। परंतु घातांक में 2^(n+1) = 2 · 2^n = Θ(2^n) होता है, जबकि 3^n और 2^n समतुल्य नहीं हैं क्योंकि (3/2)^n → ∞।
Syntax, Formula & Technical Example (Asymptotic Notations: Big-O, Big-Omega (Ω), Big-Theta (Θ))
# Formal Limit & Inequality Verification Summary:
# Big-O : 0 <= f(n) <= c * g(n) (analogy: f <= g)
# Big-Omega : 0 <= c * g(n) <= f(n) (analogy: f >= g)
# Big-Theta : c1 * g(n) <= f(n) <= c2 * g(n)(analogy: f == g)
# Little-o : lim_{n->inf} f(n)/g(n) == 0 (analogy: f < g)
# Little-w : lim_{n->inf} f(n)/g(n) == inf (analogy: f > g)
Asymptotic Notations: Big-O, Big-Omega (Ω), Big-Theta (Θ) Quick Reference & Comparison Table
| Asymptotic Notation | Mathematical Definition / Limit | Relational Analogy & Tightness |
|---|---|---|
| Big-O: O(g(n)) | 0 <= f(n) <= c * g(n) for all n >= n0 (c > 0) | Upper bound (<=); may be tight or loose |
| Big-Omega: Ω(g(n)) | 0 <= c * g(n) <= f(n) for all n >= n0 (c > 0) | Lower bound (>=); minimum required growth |
| Big-Theta: Θ(g(n)) | c1 * g(n) <= f(n) <= c2 * g(n) for all n >= n0 | Tight bound (=); holds iff both O and Ω hold |
| Little-o: o(g(n)) | lim(n -> inf) f(n) / g(n) = 0 strictly | Strict upper bound (<); 5n = o(n^2) but != o(n) |
Asymptotic Notations: Big-O, Big-Omega (Ω), Big-Theta (Θ) Top 20 Bilingual MCQs with Answers
Q1. Which mathematical inequality defines Big-O notation f(n) = O(g(n))?
(Big-O नोटेशन f(n) = O(g(n)) की सही गणितीय असमानता कौन सी है?)
(A) There exist constants c > 0 and n0 >= 1 such that 0 <= f(n) <= c * g(n) for all n >= n0
(B) f(n) == g(n) for all n >= 0
(C) 0 <= c * g(n) <= f(n) for all n >= n0
(D) lim f(n)/g(n) == infinity
Correct Answer: (A)
[EN] Big-O establishes an asymptotic upper bound capped by a constant multiple of g(n).
[HI] Big-O एक उच्चतम सीमा (Upper Bound) है जहाँ बड़े n के लिए f(n) हमेशा c * g(n) से कम या बराबर रहता है।
Q2. If f(n) = O(g(n)) AND f(n) = Ω(g(n)) both hold simultaneously, which relation is guaranteed?
(यदि f(n) = O(g(n)) और f(n) = Ω(g(n)) दोनों एक साथ सत्य हों, तो क्या निश्चित है?)
(A) f(n) = ω(g(n))
(B) f(n) < g(n) always
(C) f(n) = o(g(n))
(D) f(n) = Θ(g(n))
Correct Answer: (D)
[EN] Satisfying both an upper bound O and lower bound Ω by the same function g(n) defines Big-Theta (tight bound).
[HI] एक ही फलन g(n) से ऊपरी और निचली दोनों सीमाएं संतुष्ट होने पर उसे सटीक सीमा Big-Theta (Θ) कहते हैं।
Q3. What is the tight Big-Theta bound for f(n) = 7n^3 + 250n^2 + 8000 log(n) + 99?
(f(n) = 7n^3 + 250n^2 + 8000 log(n) + 99 की सटीक Big-Theta (Θ) सीमा क्या है?)
(A) Θ(n^5)
(B) Θ(log n)
(C) Θ(n^2)
(D) Θ(n^3)
Correct Answer: (D)
[EN] Drop lower-order terms (n^2, log n, 99) and the leading constant coefficient (7) to obtain Θ(n^3).
[HI] छोटे पदों और स्थिरांक गुणांक 7 को हटाने पर सबसे बड़ा पद Θ(n^3) बचता है।
Q4. Which growth-rate sequence is strictly ordered from FASTEST efficiency (slowest growth) to SLOWEST efficiency?
(सबसे कम वृद्धि दर (सबसे तेज़ एल्गोरिदम) से सबसे अधिक वृद्धि दर का सही आरोही क्रम कौन सा है?)
(A) 1 < sqrt(n) < log n < n < n log n < n^2 < n! < 2^n
(B) 1 < log n < n < sqrt(n) < n^2 < n log n < 2^n < n!
(C) log n < 1 < n < sqrt(n) < n^2 < 2^n < n!
(D) 1 < log n < sqrt(n) < n < n log n < n^2 < 2^n < n!
Correct Answer: (D)
[EN] Note log n grows much slower than sqrt(n), and 2^n grows slower than n! asymptotically.
[HI] सही बढ़ता क्रम: 1 < log n < √n < n < n log n < n^2 < 2^n < n! होता है।
Q5. Mathematically, is f(n) = 3n + 10 a member of O(n^2)?
(गणितीय रूप से क्या f(n) = 3n + 10 के लिए f(n) = O(n^2) लिखना सत्य है?)
(A) Only when n < 3
(B) No — Big-O allows ONLY the single tightest function
(C) Yes — 3n + 10 <= n^2 for all n >= 4, so n^2 is a valid (though non-tight) upper bound
(D) Impossible because polynomial degrees differ
Correct Answer: (C)
[EN] Big-O resembles '<='; while Θ(n) is tighter, O(n^2) is technically true since Big-O denotes any valid upper bound.
[HI] Big-O 'से कम या बराबर' जैसा होता है, इसलिए तकनीकी रूप से n^2 भी 3n+10 की एक वैध ऊपरी सीमा (Upper bound) है।
Q6. Which statement about Little-o notation is TRUE for f(n) = 4n + 5?
(f(n) = 4n + 5 के लिए Little-o (o) नोटेशन का कौन सा कथन सत्य है?)
(A) 4n + 5 = o(n^2) is TRUE, while 4n + 5 = o(n) is FALSE
(B) 4n + 5 = o(1) is TRUE
(C) 4n + 5 = o(n) is TRUE
(D) 4n + 5 = o(log n) is TRUE
Correct Answer: (A)
[EN] lim (4n+5)/n = 4 != 0 (so NOT o(n)), whereas lim (4n+5)/n^2 = 0 (so o(n^2)).
[HI] Little-o के लिए सीमा 0 आनी चाहिए: (4n+5)/n -> 4 != 0, पर (4n+5)/n^2 -> 0 आता है।
Q7. Which asymptotic relation correctly compares 3^n and 2^n?
(3^n और 2^n की सही एसिम्प्टोटिक तुलना क्या है?)
(A) 3^n = o(2^n)
(B) 2^n = o(3^n) — exponential functions with distinct bases are NOT Big-Theta equivalent
(C) 3^n = O(2^n)
(D) 3^n = Θ(2^n)
Correct Answer: (B)
[EN] Ratio 2^n / 3^n = (2/3)^n -> 0, proving 2^n grows strictly slower than 3^n.
[HI] (2/3)^n का मान अनंत पर 0 हो जाता है, अतः 2^n की वृद्धि 3^n से कड़ाई से कम है (2^n = o(3^n))।
Q8. How do log_2(n) and log_10(n) relate asymptotically?
(log_2(n) और log_10(n) एसिम्प्टोटिक रूप से किस प्रकार संबंधित हैं?)
(A) log_2(n) = ω(log_10(n))
(B) log_2(n) = o(log_10(n))
(C) log_2(n) = Θ(log_10(n))
(D) Incomparable asymptotically
Correct Answer: (C)
[EN] By change of base, log_2(n) = log_2(10) * log_10(n) ≈ 3.322 * log_10(n), differing solely by a constant.
[HI] लॉग आधार बदलने पर केवल एक स्थिरांक गुणांक log_2(10) का अंतर आता है, इसलिए दोनों Θ-समतुल्य हैं।
Q9. Why is saying 'Big-O means Worst-Case Time Complexity' a common misconception?
('Big-O का अर्थ हमेशा वर्स्ट-केस टाइम कॉम्प्लेक्सिटी होता है'—यह कथन एक भ्रांति क्यों है?)
(A) Because Big-O only describes Space Complexity
(B) Because Worst-Case uses only Big-Omega
(C) Because Big-O actually means Best-Case only
(D) Big-O is a mathematical upper-bound notation that can describe Best-Case, Average-Case, or Worst-Case functions
Correct Answer: (D)
[EN] For instance, Best-Case Bubble Sort with early exit takes O(n) (and Θ(n)) time, while Worst-Case takes O(n^2).
[HI] Big-O केवल एक गणितीय सीमा संकेतन है—इसे बेस्ट-केस (जैसे O(n)) या वर्स्ट-केस (O(n^2)) किसी के लिए भी उपयोग कर सकते हैं।
Q10. Compare 2^(n+1) and 2^n asymptotically.
(2^(n+1) और 2^n की सही एसिम्प्टोटिक तुलना क्या है?)
(A) 2^(n+1) = ω(2^n)
(B) 2^(n+1) = Θ(4^n)
(C) 2^(n+1) = Θ(2^n)
(D) 2^(n+1) = o(2^n)
Correct Answer: (C)
[EN] Since 2^(n+1) = 2 * 2^n, they differ only by a constant factor of 2, making them Θ-equivalent!
[HI] 2^(n+1) = 2 * 2^n में केवल स्थिरांक 2 का अंतर है, इसलिए 2^(n+1) = Θ(2^n) होता है!
Q11. What is the proven asymptotic lower bound for ANY comparison-based sorting algorithm on n elements?
(n तत्वों को सॉर्ट करने वाले किसी भी तुलना-आधारित (Comparison-based) एल्गोरिदम की सिद्ध न्यूनतम सीमा (Lower Bound) क्या है?)
(A) Ω(log n)
(B) Ω(n log n)
(C) Ω(n)
(D) Ω(n^2)
Correct Answer: (B)
[EN] Decision-tree height log_2(n!) = Ω(n log n) proves no comparison sort can run faster in the worst/average case.
[HI] डिसिजन ट्री की न्यूनतम ऊँचाई log_2(n!) = Ω(n log n) होती है।
Q12. Between n^(log_2 n) and 2^n, which grows asymptotically faster as n -> infinity?
(n^(log_2 n) और 2^n में से अनंत की ओर बढ़ते n के लिए कौन अधिक तेज़ी से बढ़ता है?)
(A) 2^n grows strictly faster (n^(log n) = o(2^n))
(B) Both are Θ-equivalent
(C) n^(log n) = Θ(n)
(D) n^(log n) grows strictly faster
Correct Answer: (A)
[EN] Taking log_2 of both gives (log_2 n)^2 vs n; since polylogarithmic (log n)^2 = o(n), n^(log n) = o(2^n).
[HI] दोनों का लॉग लेने पर (log n)^2 बनाम n मिलता है; चूँकि (log n)^2 < n, इसलिए 2^n कहीं अधिक तेज़ बढ़ता है।
Q13. Using the limit rule for Little-omega, when is f(n) = ω(g(n)) true?
(लिमिट नियम के अनुसार f(n) = ω(g(n)) कब सत्य होता है?)
(A) lim(n -> inf) f(n) / g(n) = 1
(B) lim(n -> inf) f(n) / g(n) = 0
(C) lim(n -> inf) f(n) - g(n) = 0
(D) lim(n -> inf) f(n) / g(n) = infinity
Correct Answer: (D)
[EN] Little-omega implies f(n) dominates g(n) strictly faster than any constant multiplier.
[HI] Little-omega का अर्थ है कि f(n) हमेशा g(n) से कड़ाई से बड़ा है, इसलिए अनुपात की सीमा ∞ आती है।
Q14. Using the Master Theorem, what is the tight asymptotic bound of T(n) = 2T(n/2) + Θ(n) (e.g., Merge Sort)?
(मास्टर थ्योरम के अनुसार पुनरावृत्ति समीकरण T(n) = 2T(n/2) + Θ(n) का सटीक मान क्या होगा?)
(A) Θ(n)
(B) Θ(n^2)
(C) Θ(log n)
(D) Θ(n log n)
Correct Answer: (D)
[EN] Here a=2, b=2, so n^(log_b a) = n^1, matching f(n) = Θ(n) (Master Theorem Case 2) -> Θ(n log n).
[HI] मास्टर थ्योरम केस-2 (n^(log_2 2) = n = f(n)) के अनुसार उत्तर Θ(n log n) आता है।
Q15. Order 2^n, n!, and n^n from smallest to largest asymptotic growth.
(2^n, n! और n^n को सबसे कम से सबसे अधिक वृद्धि दर के क्रम में लगाएं।)
(A) 2^n < n^n < n!
(B) n^n < n! < 2^n
(C) n! < 2^n < n^n
(D) 2^n < n! < n^n
Correct Answer: (D)
[EN] By Stirling's approximation, n! ≈ √(2πn) * (n/e)^n, strictly outgrowing 2^n while staying below n^n.
[HI] स्टर्लिंग सूत्र से n! का मान 2^n से बड़ा लेकिन n^n से छोटा होता है (2^n < n! < n^n)।
Q16. Which statement is NOT true regarding Asymptotic Notations?
(एसिम्प्टोटिक नोटेशन्स के बारे में निम्नलिखित में से कौन सा कथन असत्य (NOT true) है?)
(A) 2^(n+1) = ω(2^n) because the exponent increased by 1
(B) Little-o denotes a strictly smaller growth rate where limit f(n)/g(n) = 0
(C) Big-O drops constant coefficients and lower-order polynomial terms
(D) Every f(n) = Θ(g(n)) automatically satisfies both f(n) = O(g(n)) and f(n) = Ω(g(n))
Correct Answer: (A)
[EN] 2^(n+1) = 2 * 2^n, which differs only by constant 2—meaning 2^(n+1) = Θ(2^n), NOT ω(2^n)!
[HI] 2^(n+1) = 2 * 2^n में केवल स्थिरांक 2 का गुणक है, अतः यह Θ(2^n) है न कि ω(2^n)।
Q17. Within Asymptotic Notations: Big-O, Big-Omega (Ω), Big-Theta (Θ), which asymptotic notation directly maps to: "0 <= f(n) <= c * g(n) for all n >= n0 (c > 0)"?
(Asymptotic Notations: Big-O, Big-Omega (Ω), Big-Theta (Θ) में कौन सा Asymptotic Notation सीधे "0 <= f(n) <= c * g(n) for all n >= n0 (c > 0)" से संबंधित है?)
(A) Little-o: o(g(n))
(B) Big-O: O(g(n))
(C) Big-Theta: Θ(g(n))
(D) Big-Omega: Ω(g(n))
Correct Answer: (B)
[EN] In Asymptotic Notations: Big-O, Big-Omega (Ω), Big-Theta (Θ), 'Big-O: O(g(n))' handles '0 <= f(n) <= c * g(n) for all n >= n0 (c > 0)' (Upper bound (<=); may be tight or loose).
[HI] Asymptotic Notations: Big-O, Big-Omega (Ω), Big-Theta (Θ) में 'Big-O: O(g(n))' का कार्य/विवरण '0 <= f(n) <= c * g(n) for all n >= n0 (c > 0)' (Upper bound (<=); may be tight or loose) है।
Q18. Which option accurately describes 'Big-Omega: Ω(g(n))' in Asymptotic Notations: Big-O, Big-Omega (Ω), Big-Theta (Θ)?
(Asymptotic Notations: Big-O, Big-Omega (Ω), Big-Theta (Θ) के संदर्भ में 'Big-Omega: Ω(g(n))' की सही विशेषता कौन सी है?)
(A) c1 * g(n) <= f(n) <= c2 * g(n) for all n >= n0
(B) 0 <= c * g(n) <= f(n) for all n >= n0 (c > 0)
(C) lim(n -> inf) f(n) / g(n) = 0 strictly
(D) 0 <= f(n) <= c * g(n) for all n >= n0 (c > 0)
Correct Answer: (B)
[EN] 'Big-Omega: Ω(g(n))' provides '0 <= c * g(n) <= f(n) for all n >= n0 (c > 0)' — key point: Lower bound (>=); minimum required growth.
[HI] 'Big-Omega: Ω(g(n))' का मुख्य विवरण '0 <= c * g(n) <= f(n) for all n >= n0 (c > 0)' है (Lower bound (>=); minimum required growth)।
Q19. In Asymptotic Notations: Big-O, Big-Omega (Ω), Big-Theta (Θ), identify the correct parameter for the specification: "c1 * g(n) <= f(n) <= c2 * g(n) for all n >= n0".
(Asymptotic Notations: Big-O, Big-Omega (Ω), Big-Theta (Θ) में "c1 * g(n) <= f(n) <= c2 * g(n) for all n >= n0" विवरण किस विकल्प के लिए सही है?)
(A) Big-Omega: Ω(g(n))
(B) Big-Theta: Θ(g(n))
(C) Big-O: O(g(n))
(D) Little-o: o(g(n))
Correct Answer: (B)
[EN] 'Big-Theta: Θ(g(n))' corresponds to 'c1 * g(n) <= f(n) <= c2 * g(n) for all n >= n0' (Tight bound (=); holds iff both O and Ω hold).
[HI] 'Big-Theta: Θ(g(n))' का संबंध 'c1 * g(n) <= f(n) <= c2 * g(n) for all n >= n0' (Tight bound (=); holds iff both O and Ω hold) से है।
Q20. Considering Asymptotic Notations: Big-O, Big-Omega (Ω), Big-Theta (Θ), what key behavior defines 'Little-o: o(g(n))'?
(Asymptotic Notations: Big-O, Big-Omega (Ω), Big-Theta (Θ) में 'Little-o: o(g(n))' की मुख्य भूमिका या मान क्या है?)
(A) 0 <= c * g(n) <= f(n) for all n >= n0 (c > 0)
(B) lim(n -> inf) f(n) / g(n) = 0 strictly
(C) c1 * g(n) <= f(n) <= c2 * g(n) for all n >= n0
(D) 0 <= f(n) <= c * g(n) for all n >= n0 (c > 0)
Correct Answer: (B)
[EN] 'Little-o: o(g(n))' represents 'lim(n -> inf) f(n) / g(n) = 0 strictly' (Strict upper bound (<); 5n = o(n^2) but != o(n)).
[HI] 'Little-o: o(g(n))' का अर्थ/मान 'lim(n -> inf) f(n) / g(n) = 0 strictly' है (Strict upper bound (<); 5n = o(n^2) but != o(n))।
Asymptotic Notations: Big-O, Big-Omega (Ω), Big-Theta (Θ) — Exam FAQs
Q1: Is Big-O always identical to Worst-Case complexity?
क्या Big-O और वर्स्ट-केस कॉम्प्लेक्सिटी हमेशा एक ही चीज़ होते हैं?
[EN] No! Best-Case, Average-Case, and Worst-Case describe *which input scenario* you analyze, while Big-O, Big-Omega, and Big-Theta describe *mathematical bounds* (upper, lower, tight) for any of those scenarios.
[HI] नहीं! बेस्ट, एवरेज और वर्स्ट केस इनपुट की *स्थिति* बताते हैं, जबकि Big-O, Omega और Theta उन स्थितियों की *गणितीय सीमाएं* (ऊपरी, निचली, सटीक) दर्शाते हैं।
Q2: What is the practical difference between Big-O and Big-Theta?
Big-O और Big-Theta के बीच व्यावहारिक अंतर क्या है?
[EN] Big-O only guarantees an upper cap (saying Linear Search is O(n^2) is technically true, even though imprecise), whereas Big-Theta pins down BOTH upper and lower bounds tightly (Linear Search worst case is strictly Θ(n)).
[HI] Big-O केवल ऊपरी सीमा बताता है (तकनीकी रूप से O(n^2) भी गलत नहीं), जबकि Big-Theta सटीक बराबर वृद्धि दर (Θ(n)) बताता है।
Q3: Why can we ignore logarithm bases in Big-O (log2 n vs log10 n), yet NOT ignore exponential bases (2^n vs 3^n)?
Big-O में लॉग का आधार (log2 n बनाम log10 n) अनदेखा हो जाता है, पर घातांक का आधार (2^n बनाम 3^n) क्यों नहीं?
[EN] Changing a log base only multiplies the whole function by a fixed constant (log_2(10) ≈ 3.32), which Big-O absorbs. In contrast, 3^n / 2^n = 1.5^n grows exponentially without bound instead of staying constant!
[HI] लॉग का आधार बदलने पर केवल एक निश्चित स्थिरांक का गुणा होता है जिसे Big-O छोड़ देता है, परंतु 3^n / 2^n = (1.5)^n अनंत तक बढ़ता है न कि स्थिरांक रहता है।
Post a Comment
Post a Comment