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 , it would be incorrect to say that binary search runs in time in all cases. What if we find the target value upon the first guess? Then it runs in time. The running time of binary search is never worse than , 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" অথবা শুধু " এর 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. We can make a stronger statement about the worst-case running time: it's . But for a blanket statement that covers all cases, the strongest statement we can make is that binary search runs in 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 in a particular situation, then it's also . For example, we can say that because the worst-case running time of binary search is , it's also .
The converse is not necessarily true: as we've seen, we can say that binary search always runs in time but not that it always runs in 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 time. That's because the running time grows no faster than a constant times . 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 is an upper bound on the running time of binary search. Other, imprecise, upper bounds on binary search would be , , and . But none of , , , and would be correct to describe the running time of binary search in any case.