অ্যাসিম্পটোটিক নোটেশন

অ্যাসিম্পটোটিক নোটেশন

অ্যালগরিদমের কমপ্লেক্সিটি অ্যাসিম্পটোটিক অ্যানালিসিসের জন্য উপস্থাপন করতে অ্যাসিম্পটোটিক নোটেশন ব্যবহৃত হয়। এই নোটেশনগুলো কমপ্লেক্সিটি উপস্থাপনের গাণিতিক টুল। তিনটি সাধারণভাবে ব্যবহৃত নোটেশন রয়েছে।

বিগ-ও নোটেশন

বিগ-ও (O) নোটেশন একটি ফাংশন f(n)-র জন্য একটি কনস্ট্যান্ট ফ্যাক্টরের মধ্যে আপার বাউন্ড দেয়।

আমরা লিখি f(n) = O(g(n)), যদি পজিটিভ কনস্ট্যান্ট n0 এবং c থাকে যাতে, n0-এর ডানে f(n) সবসময় c*g(n)-র ওপর বা নিচে থাকে।

O(g(n)) = { f(n) : ধনাত্মক কনস্ট্যান্ট c এবং n0 আছে যাতে 0 ≤ f(n) ≤ c g(n), সকল n ≥ n0 এর জন্য }

বিগ-ওমেগা নোটেশন

বিগ-ওমেগা (Ω) নোটেশন একটি ফাংশন 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 এর জন্য }