অ্যাসিম্পটোটিক নোটেশন
অ্যালগরিদমের কমপ্লেক্সিটি অ্যাসিম্পটোটিক অ্যানালিসিসের জন্য উপস্থাপন করতে অ্যাসিম্পটোটিক নোটেশন ব্যবহৃত হয়। এই নোটেশনগুলো কমপ্লেক্সিটি উপস্থাপনের গাণিতিক টুল। তিনটি সাধারণভাবে ব্যবহৃত নোটেশন আছে।
বিগ ওমেগা নোটেশন
বিগ-ওমেগা (Ω) নোটেশন একটি ফাংশন f(n)-র জন্য একটি কনস্ট্যান্ট ফ্যাক্টরের মধ্যে লোয়ার বাউন্ড দেয়।
আমরা লিখি f(n) = Ω(g(n)), যদি পজিটিভ কনস্ট্যান্ট n0 এবং c থাকে যাতে, n0-এর ডানে f(n) সবসময় c*g(n)-র ওপর বা নিচে থাকে।
Ω(g(n)) = { f(n) : ধনাত্মক কনস্ট্যান্ট c এবং n0 আছে যাতে 0 ≤ c g(n) ≤ f(n), সকল n ≤ n0 এর জন্য }
বিগ থেটা নোটেশন
বিগ-থেটা (Θ) নোটেশন একটি ফাংশন f(n)-র জন্য একটি কনস্ট্যান্ট ফ্যাক্টরের মধ্যে বাউন্ড দেয়।
আমরা লিখি f(n) = Θ(g(n)), যদি পজিটিভ কনস্ট্যান্ট n0 এবং c1 এবং c2 থাকে যাতে, n0-এর ডানে f(n) সবসময় c1*g(n) এবং c2*g(n)-র মধ্যে থাকে।
Θ(g(n)) = {f(n) : ধনাত্মক কনস্ট্যান্ট c1, c2 এবং n0 আছে যাতে 0 ≤ c1 g(n) ≤ f(n) ≤ c2 g(n), সকল n ≥ n0 এর জন্য }
