31
$\begingroup$

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?

$\endgroup$
  • $\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$ – tanmoy Mar 26 '14 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$ – tanmoy Mar 26 '14 at 14:50
  • 5
    $\begingroup$ $O(\log_2 n)$ is not more specific than $O(\log n)$, they denote the same class of functions. $\endgroup$ – Raphael Mar 26 '14 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$ – ctrl-alt-delor Jun 2 at 7:41
39
$\begingroup$

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)$.

$\endgroup$
  • $\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 Feb 21 '16 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 Feb 22 '16 at 7:32
17
$\begingroup$

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

Contrive(n)
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.

$\endgroup$
  • 1
    $\begingroup$ To make this deterministic, split along $n \bmod 4$ cases. $\endgroup$ – vonbrand Aug 26 '15 at 20:54
4
$\begingroup$

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$.)

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\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 Oct 14 '18 at 17:25
  • $\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$ – Hamed Nassar Oct 18 '18 at 20:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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