অ্যাসিম্পটোটিক নোটেশন
অ্যালগরিদমের কমপ্লেক্সিটি অ্যাসিম্পটোটিক অ্যানালিসিসের জন্য উপস্থাপন করতে অ্যাসিম্পটোটিক নোটেশন ব্যবহৃত হয়। এই নোটেশনগুলো কমপ্লেক্সিটি উপস্থাপনের গাণিতিক টুল। তিনটি সাধারণভাবে ব্যবহৃত নোটেশন আছে।
বিগ ও নোটেশন
বিগ-ও (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 এর জন্য }
