Big-O প্রতীক

We use big-Θ notation to asymptotically bound the growth of a running time to within constant factors above and below. Sometimes we want to bound from only above.

For example, although the worst-case running time of binary search is $\mathrm{\Theta }({\log }_{2}n)$‍, it would be incorrect to say that binary search runs in $\mathrm{\Theta }({\log }_{2}n)$‍ time in all cases. What if we find the target value upon the first guess? Then it runs in $\mathrm{\Theta }(1)$‍ time. The running time of binary search is never worse than $\mathrm{\Theta }({\log }_{2}n)$‍, but it's sometimes better.

It would be convenient to have a form of asymptotic notation that means "the running time grows at most this much, but it could grow more slowly." We use "big-O" notation for just such occasions.

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

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

Now we have a way to characterize the running time of binary search in all cases. We can say that the running time of binary search is always $O({\log }_{2}n)$‍. We can make a stronger statement about the worst-case running time: it's $\mathrm{\Theta }({\log }_{2}n)$‍. But for a blanket statement that covers all cases, the strongest statement we can make is that binary search runs in $O({\log }_{2}n)$‍ time.

If you go back to the definition of big-Θ notation, you'll notice that it looks a lot like big-O notation, except that big-Θ notation bounds the running time from both above and below, rather than just from above. If we say that a running time is $\mathrm{\Theta }(f(n))$‍ in a particular situation, then it's also $O(f(n))$‍. For example, we can say that because the worst-case running time of binary search is $\mathrm{\Theta }({\log }_{2}n)$‍, it's also $O({\log }_{2}n)$‍.

The converse is not necessarily true: as we've seen, we can say that binary search always runs in $O({\log }_{2}n)$‍ time but not that it always runs in $\mathrm{\Theta }({\log }_{2}n)$‍ time.

Because big-O notation gives only an asymptotic upper bound, and not an asymptotically tight bound, we can make statements that at first glance seem incorrect, but are technically correct. For example, it is absolutely correct to say that binary search runs in $O(n)$‍ time. That's because the running time grows no faster than a constant times $n$‍. In fact, it grows slower.

Think of it this way. Suppose you have 10 dollars in your pocket. You go up to your friend and say, "I have an amount of money in my pocket, and I guarantee that it's no more than one million dollars." Your statement is absolutely true, though not terribly precise.

One million dollars is an upper bound on 10 dollars, just as $O(n)$‍ is an upper bound on the running time of binary search. Other, imprecise, upper bounds on binary search would be $O(n^2)$‍, $O(n^3)$‍, and $O(2^n)$‍. But none of $\mathrm{\Theta }(n)$‍, $\mathrm{\Theta }(n^2)$‍, $\mathrm{\Theta }(n^3)$‍, and $\mathrm{\Theta }(2^n)$‍ would be correct to describe the running time of binary search in any case.

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