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 $\Theta(\log_2 n)$\Theta, left parenthesis, log, start base, 2, end base, n, right parenthesis, it would be incorrect to say that binary search runs in $\Theta(\log_2 n)$\Theta, left parenthesis, log, start base, 2, end base, n, right parenthesis time in all cases. What if we find the target value upon the first guess? Then it runs in $\Theta(1)$\Theta, left parenthesis, 1, right parenthesis time. The running time of binary search is never worse than $\Theta(\log_2 n)$\Theta, left parenthesis, log, start base, 2, end base, n, right parenthesis, 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))$O, left parenthesis, f, left parenthesis, n, right parenthesis, right parenthesis হয়, তাহলে যথেষ্ট বড় $n$n এর ক্ষেত্রে, সর্বোচ্চ চলার সময় হবে $k \cdot f(n)$k, dot, f, left parenthesis, n, right parenthesis যেখানে $k$k হল একটি ধ্রুবক। এখানে $O(f(n))$O, left parenthesis, f, left parenthesis, n, right parenthesis, right parenthesis চলার সময়কে দেখানো হল:

আমরা বলি যে, চলার সময় হল "$f(n)$f, left parenthesis, n, right parenthesis এর বড়-O" অথবা শুধু "$f(n)$f, left parenthesis, n, right parenthesis এর 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)$O, left parenthesis, log, start base, 2, end base, n, right parenthesis. We can make a stronger statement about the worst-case running time: it's $\Theta(\log_2 n)$\Theta, left parenthesis, log, start base, 2, end base, n, right parenthesis. 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)$O, left parenthesis, log, start base, 2, end base, n, right parenthesis 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 $\Theta(f(n))$\Theta, left parenthesis, f, left parenthesis, n, right parenthesis, right parenthesis in a particular situation, then it's also $O(f(n))$O, left parenthesis, f, left parenthesis, n, right parenthesis, right parenthesis. For example, we can say that because the worst-case running time of binary search is $\Theta(\log_2 n)$\Theta, left parenthesis, log, start base, 2, end base, n, right parenthesis, it's also $O(\log_2 n)$O, left parenthesis, log, start base, 2, end base, n, right parenthesis.

The converse is not necessarily true: as we've seen, we can say that binary search always runs in $O(\log_2 n)$O, left parenthesis, log, start base, 2, end base, n, right parenthesis time but not that it always runs in $\Theta(\log_2 n)$\Theta, left parenthesis, log, start base, 2, end base, n, right parenthesis 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)$O, left parenthesis, n, right parenthesis time. That's because the running time grows no faster than a constant times $n$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)$O, left parenthesis, n, right parenthesis is an upper bound on the running time of binary search. Other, imprecise, upper bounds on binary search would be $O(n^2)$O, left parenthesis, n, squared, right parenthesis, $O(n^3)$O, left parenthesis, n, cubed, right parenthesis, and $O(2^n)$O, left parenthesis, 2, start superscript, n, end superscript, right parenthesis. But none of $\Theta(n)$\Theta, left parenthesis, n, right parenthesis, $\Theta(n^2)$\Theta, left parenthesis, n, squared, right parenthesis, $\Theta(n^3)$\Theta, left parenthesis, n, cubed, right parenthesis, and $\Theta(2^n)$\Theta, left parenthesis, 2, start superscript, n, end superscript, right parenthesis 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 দিয়ে লাইসেন্সকৃত।