एसिम्प्टोटिक नोटेशन
एसिम्प्टोटिक नोटेशन एल्गोरिदम की जटिलताओं को एसिम्प्टोटिक विश्लेषण के लिए दर्शाने के लिए उपयोग किए जाते हैं। ये नोटेशन जटिलताओं को दर्शाने के लिए गणितीय उपकरण हैं। तीन नोटेशन आमतौर पर उपयोग किए जाते हैं।
बिग ओ नोटेशन (Big-Oh)
बिग-ओह (O) नोटेशन एक फंक्शन f(n) के लिए एक कॉन्स्टेंट फैक्टर के भीतर ऊपरी सीमा देता है।
हम f(n) = O(g(n)) लिखते हैं, यदि पॉजिटिव कॉन्स्टेंट n₀ और c मौजूद हैं जैसे कि, n₀ के दाईं ओर f(n) हमेशा c*g(n) पर या नीचे रहता है।
O(g(n)) = { f(n) : पॉजिटिव कॉन्स्टेंट c और n₀ मौजूद हैं जैसे कि 0 ≤ f(n) ≤ c g(n), सभी n ≥ n₀ के लिए }
बिग ओमेगा नोटेशन (Big-Omega)
बिग-ओमेगा (Ω) नोटेशन एक फंक्शन f(n) के लिए एक कॉन्स्टेंट फैक्टर के भीतर निचली सीमा देता है।
हम f(n) = Ω(g(n)) लिखते हैं, यदि पॉजिटिव कॉन्स्टेंट n₀ और c मौजूद हैं जैसे कि, n₀ के दाईं ओर f(n) हमेशा c*g(n) पर या ऊपर रहता है।
Ω(g(n)) = { f(n) : पॉजिटिव कॉन्स्टेंट c और n₀ मौजूद हैं जैसे कि 0 ≤ c g(n) ≤ f(n), सभी n ≥ n₀ के लिए }
बिग थीटा नोटेशन (Big-Theta)
बिग-थीटा (Θ) नोटेशन एक फंक्शन f(n) के लिए एक कॉन्स्टेंट फैक्टर के भीतर तंग सीमा (टाइट बाउंड) देता है।
हम f(n) = Θ(g(n)) लिखते हैं, यदि पॉजिटिव कॉन्स्टेंट n₀, c₁ और c₂ मौजूद हैं जैसे कि, n₀ के दाईं ओर f(n) हमेशा c₁*g(n) और c₂*g(n) के बीच समावेशी रूप से रहता है।
Θ(g(n)) = {f(n) : पॉजिटिव कॉन्स्टेंट c₁, c₂ और n₀ मौजूद हैं जैसे कि 0 ≤ c₁ g(n) ≤ f(n) ≤ c₂ g(n), सभी n ≥ n₀ के लिए}
