Big-Ω (বড়-ওমেগা) প্রতীক

অনেক সময়, আমরা বলতে চাই যে, কোন ঊর্ধ্বসীমা ব্যতিত একটি অ্যালগোরিদমের কমপক্ষে কিছু সময় লাগে। আমরা বড়-Ω চিহ্ন ব্যবহার করি; এটি হল গ্রীক অক্ষর "ওমেগা"।

যদি চলার সময় $\mathrm{\Omega }(f(n))$‍ হয়, তাহলে যথেষ্ট বড় $n$‍ এর ক্ষেত্রে, কমপক্ষে চলার সময় হবে $k\cdot f(n)$‍ যেখানে $k$‍ হল একটি ধ্রুবক। এখানে $\mathrm{\Omega }(f(n))$‍ চলার সময়কে দেখানো হল:

আমরা বলি যে, চলার সময় হল $f(n)$‍ এর "বড়-Ω"। আমরা অ্যাসিম্পটোটিক নিম্নসীমার জন্য বড়-Ω চিহ্ন ব্যবহার করি, কারণ বড় ইনপুটের ক্ষেত্রে চলার সময় নিচের থেকে শুরু হয়।

Just as $\mathrm{\Theta }(f(n))$‍ automatically implies $O(f(n))$‍, it also automatically implies $\mathrm{\Omega }(f(n))$‍. So we can say that the worst-case running time of binary search is $\mathrm{\Omega }({\log }_{2}n)$‍.

We can also make correct, but imprecise, statements using big-Ω notation. For example, if you really do have a million dollars in your pocket, you can truthfully say "I have an amount of money in my pocket, and it's at least 10 dollars." That is correct, but certainly not very precise. Similarly, we can correctly but imprecisely say that the worst-case running time of binary search is $\mathrm{\Omega }(1)$‍, because we know that it takes at least constant time.

Of course, typically, when we are talking about algorithms, we try to describe their running time as precisely as possible. We provide the examples of the imprecise statements here to help you better understand big-$\mathrm{\Omega }$‍, big-$O$‍, and big-$\mathrm{\Theta }$‍.

এই বিষয়বস্তুটি Dartmouth Computer Science এর প্রফেসর Thomas Cormen এবং Devin Balkcom এর সহযোগিতায় এবং একই সাথে খান একাডেমির কম্পিউটিং শিক্ষাক্রম দলের একসাথে কাজ করার মাধ্যমে তৈরি করা হয়েছে। এই বিষয়বস্তু CC-BY-NC-SA দিয়ে লাইসেন্সকৃত।