Today we discussed in a lecture a very simple algorithm for finding an element in a sorted array using binary search. We were asked to determine its asymptotic complexity for an array of $n$ elements.

My idea was, that it is obvisously $O(\log n)$, or $O(\log_2 n)$ to be more specific because $\log_2 n$ is the number of operations in the worst case. But I can do better, for example if I hit the searched element the first time - then the lower bound is $\Omega(1)$.

The lecturer presented the solution as $\Theta(\log n)$ since we usually consider only worst case inputs for algorithms.

But when considering only worst cases, whats the point of having $O$ and $\Omega$-notation when all worst cases of the given problem have the same complexity ($\Theta$ would be all we need, right?).

What am I missing here?

  • $\begingroup$ @Smaji: What do you mean by "But when considering only worst cases, whats the point of having big O and big Omega notation when all worst cases have +- the same complexity (Theta would be all we need, right?)."please clarify it. $\endgroup$ Commented Mar 26, 2014 at 12:58
  • $\begingroup$ @Smajl:I think your question is: What is the necessity of Big O and Big Omega notation in algorithm analysis? am I correct? $\endgroup$ Commented Mar 26, 2014 at 14:50
  • 6
    $\begingroup$ $O(\log_2 n)$ is not more specific than $O(\log n)$, they denote the same class of functions. $\endgroup$
    – Raphael
    Commented Mar 26, 2014 at 15:22
  • $\begingroup$ $log_2(n)$ is the same as $log(b)/log(2) × log_b(n)$ therefore the 2 just indicates a factor, that can be remove (like other factors in big-O. $\endgroup$ Commented Jun 2, 2019 at 7:41
  • $\begingroup$ @Raphael is right. Recall the change-of-base formula: $\log_2{n} = \frac{\log{n}}{\log{2}}$. $\endgroup$ Commented Nov 30, 2020 at 3:46

4 Answers 4


Landau notation denotes asymptotic bounds on functions. See here for an explanation of the differences among $O$, $\Omega$ and $\Theta$.

Worst-, best-, average or you-name-it-case time describe distinct runtime functions: one for the sequence of highest runtime of any given $n$, one for that of lowest, and so on..

Per se, the two have nothing to do with each other. The definitions are independent. Now we can go ahead and formulate asymptotic bounds on runtime functions: upper ($O$), lower ($\Omega$) or both ($\Theta$). We can do either for worst-, best- or any other case.

For instance, in binary search we get a best-case runtime asymptotic of $\Theta(1)$ and a worst-case asymptotic of $\Theta(\log n)$.

  • 1
    $\begingroup$ The key takeaway for me is that, we can do worst-, best- case analysis on anything of the asymptotic bounded functions. To me, that shows the independence of Big O vs. worst case analysis. Thanks! $\endgroup$
    – Patrick
    Commented Feb 21, 2016 at 21:28
  • 1
    $\begingroup$ @Patrick Not quite. FIrst, you decide whether you want to analyze worst-, average- or best-case. Then you come up with the cost function (or as good an approximation as you can). Only then do you take asymptotics, if at all. $\endgroup$
    – Raphael
    Commented Feb 22, 2016 at 7:32

Consider the following algorithm (or procedure, or piece of code, or whatever):

1. if n = 0 then do something Theta(n^3)
2. else if n is even then
3.    flip a coin
4.    if heads, do something Theta(n)
5.    else if tails, do something Theta(n^2)
6. else if n is odd then
7.    flip a coin
8.    if heads, do something Theta(n^4)
9.    else if tails, do something Theta(n^5)

What is the asymptotic behavior of this function?

In the best case (where $n$ is even), the runtime is $\Omega(n)$ and $O(n^2)$, but not $\Theta$ of anything.

In the worst case (where $n$ is odd), the runtime is $\Omega(n^4)$ and $O(n^5)$, but not $\Theta$ of anything.

In the case $n = 0$, the runtime is $\Theta(n^3)$.

This is a bit of a contrived example, but only for the purposes of clearly demonstrating the differences between the bound and the case. You could have the distinction become meaningful with completely deterministic procedures, if the activities you're performing don't have any known $\Theta$ bounds.

  • 3
    $\begingroup$ To make this deterministic, split along $n \bmod 4$ cases. $\endgroup$
    – vonbrand
    Commented Aug 26, 2015 at 20:54
  • 3
    $\begingroup$ @Patrick87, read many answers, but got a complete gist from your's answer. Thanks for writing this! UPVOTED! $\endgroup$ Commented Dec 27, 2019 at 10:47
  • 1
    $\begingroup$ Well if $n = 0$, then clearly $n^3 = 0$ and so the total runtime would be $\Theta(1)$, not $\Theta(n^3) = \Theta(0)$ as the check for $n = 0$ is probably constant. $\endgroup$
    – Tyilo
    Commented Mar 30, 2021 at 15:43
  • 2
    $\begingroup$ This isn't really correct. In the best case, the number is even and the coin flip is heads; in the worst case, the number is odd and the coin flip is tails. There is no such thing as a function which is "not Theta of anything" because every function is Theta of itself. $\endgroup$
    – kaya3
    Commented Oct 9, 2022 at 0:25
  • $\begingroup$ I think it depends on the specific definition of best/worst case. Do we take into account also the outcome of the coin flip or just the value of n? In the first case, the best case would be when n=even AND coin=heads. Thus we could just split the whole procedure into 4 branches (as suggested by @vonbrand), highlighting the fact that the complexity is $\Theta(n)$ in the best case and $\Theta(n^5)$ in the worst case (as pointed out by @kaya3). Or is it? What is "do something Theta(n)" supposed to mean? Does $\Theta(n)$ refer to the complexity of something in the best or in the worst case? $\endgroup$
    – logi-kal
    Commented Apr 10 at 8:10

Not necessarily. In this case, namely binary search on a sorted array, you can see that: (a) binary search takes at most $[\log n + 1]$ steps; (b) there are inputs that actually force this many steps. So if $T(n)$ is the running time on a worst-case input for binary search, you can say that $T(n) = \Theta(\log n)$.

On the other hand, for other algorithms, you might not be able to work out $T(n)$ exactly, in which case you might have a gap between the upper and lower bounds for the running time on a worst case input.

Now, for searching a sorted array, something more is true, which is that any algorithm at all for searching a sorted array needs to inspect $[\log n + 1]$. For this kind of lower bound, you need to analyze the problem itself, though. (Here is the idea: at any time, a search algorithm hasn't ruled out some set $S\subset [n]$ of positions where the element it's looking for can be. A carefully-crafted input can then guarantee that $|S|$ is reduced by at most a factor of $2$.)


You are right, many people sloppily use $O$ when they should use $\Theta $. For example, an algorithm analyst may end up with a time function $% T(n)=n^{2}+n+2$ and immediately conclude that $T(n)=O(n^{2})$, which is technically right, but a sharper assertion would be $T(n)=\Theta (n^{2})$. I attribute this oblivious behavior to two reasons. First, many see $O$ to be more popular and acceptable, possibly because of its long history. Recall that it was introduced more than a century ago, whereas $\Theta $ (and $% \Omega $) were introduced only in 1976 (by Donald Knuth). Second, it could be because $O$ is readily available on the keyboard, whereas $\Theta $ is not!

From a technical point of view, however, the main reason careful analysts prefer to use $O$ over $\Theta $ is that the former covers "greater territory" than the latter. If we take your example of binary search and want to use $\Theta $, we will have to make two assertions:\ one for the best case, namely $\Theta (1)$, and another for the worst case, namely $% \Theta (\log n)$. With $O$, we make only one assertion, namely $O(\log n)$. Mathematically, the functions covered by $\Theta $ are also covered by $O$, whereas the converse is not necessarily true.

  • $\begingroup$ Welcome, and thanks for taking the time to post an answer! However, I can't tell what your point is here. In the first paragraph, you offer some speculation. In the second, you propose a point of view that is "sloppy" itself: saying "it is $O(\log n)$ average case" does not say anything about the best case, except that its in the same class. Saying "it is $Θ(\log n)$ average case" implies the same upper bound! If you want to impart additional information about the best case, you'll have to give it explicitly either way. Therefore, I don't see how you're making a point for using O over Θ. $\endgroup$
    – Raphael
    Commented Oct 14, 2018 at 17:25
  • 1
    $\begingroup$ @Raphael I refer you to the definitions of the two notations. Furthermore, realize that they are used to classify the asymptotic "growth rate" of the running time, not the running time itself as propagated by your various answers and comments. $\endgroup$ Commented Oct 18, 2018 at 20:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.