অ্যাসিম্পোটিক নোটেশনস
অ্যাসিম্পটোটিক বিশ্লেষণের জন্য অ্যালগরিদমের জটিলতাগুলি উপস্থাপন করতে অ্যাসিম্পোটিক নোটেশন ব্যবহার করা হয়। এই স্বরলিপিগুলি জটিলতাগুলিকে উপস্থাপন করার জন্য গাণিতিক সরঞ্জাম। তিনটি স্বরলিপি রয়েছে যা সাধারণত ব্যবহৃত হয়৷
৷বিগ ওমেগা নোটেশন
বিগ-ওমেগা (Ω) স্বরলিপি একটি ধ্রুবক ফ্যাক্টরের মধ্যে একটি ফাংশন f(n) এর জন্য একটি নিম্ন সীমা দেয়।
আমরা লিখি f(n) =Ω(g(n)), যদি n0-এর ডানদিকে ধনাত্মক ধ্রুবক n0 এবং c থাকে f(n) সবসময় c*g(n) এর উপরে বা উপরে থাকে।
Ω(g(n)) ={ f(n):এখানে ধনাত্মক ধ্রুবক c এবং n0 বিদ্যমান যাতে 0 ≤ c g(n) ≤ f(n), সমস্ত n ≤ n0 এর জন্য
বিগ থিটা নোটেশন
Big-Theta(Θ) নোটেশন একটি ফাংশন 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
