6
$\begingroup$

I mathematically understand $f(n) \in O(g(n))$ : $f(n)$ does not grow faster than $g(n)$. More formally, $\exists c, n_0$ s.t. $f(n) \leq cg(n) \forall n \geq n_0$.

Similarly, $f(n) \in \Theta(g(n))$ means that $f(n)$ grows approximately as fast as $g(n)$. i.e. $f(n) \in O(g(n)), \Omega(g(n))$.

What I don't get is why people use big Oh for the running time of an algorithm? Shouldn't we be using big Theta. When we say "Running time" of an algorithm, we refer to worst case running time i.e. $T(n) = max \{ ALG(x): |x| = n \}$.

So, ex: the worst case running time of linear search on an input of size $n$ ($n$ elements and a target value) is $\Theta(n)$ and $O(n)$, but $\Theta(n)$ gives more information. So, why do algorithm books use $O(n)$ and not $\Theta(n)$.

$\endgroup$
  • 5
    $\begingroup$ Often it's because we simply can't get a tight big-theta bound on the running time of an algorithm. If an algorithm is sufficiently complicated, it might happen that the best we can do is say the running time is, say $O(n^{n!})$ where in actuality it might be $\Theta(2^{n\log n\log\log n})$. $\endgroup$ – Rick Decker Feb 24 '16 at 19:16
  • $\begingroup$ Historical reasons. $\endgroup$ – Yuval Filmus Feb 24 '16 at 19:25
  • $\begingroup$ "What I don't get is why people use big Oh for the running time of an algorithm? Shouldn't we be using big Theta." -- Yes. Wait, not, we should make even more precise statements. But if I have to choose, yes, $\Theta$! $\endgroup$ – Raphael Feb 24 '16 at 20:38
1
$\begingroup$

I see two reasons why people prefer Big Oh over Big Theta:

  1. The runtime complexity of an algorithm is not necessarily defined as the worst-case runtime complexity. You might also just see it as the runtime on an arbitrary instance of length $n$. Then, if you write for example that the runtime $t(n)$ of an algorithm is in $\mathcal{O}(n^2)$ this means that whatever input of length $n$ you choose, it will always grow asymptotically slower than the function $c \cdot n^2$ for some constant $c$ -- so we're then obviously making a statement about the worst-case runtime.
  2. Sometimes when you analyze the runtime complexity of an algorithm you don't know for sure if the worst-case complexity you're giving is really tight. Take for example the runtime complexity of matrix multiplication. There it is still not clear if the runtime $n^{2.3728639}$ is really the worst-case. And thus the runtime is known to be in $\mathcal{O}(n^{2.3728639})$ while it's not sure if it's in $\Theta(n^{2.3728639})$.

But also, you are right that in some cases it would be better to provide a Big Theta bound than a Big Oh bound.

$\endgroup$
4
$\begingroup$

A (sloppy) upper bound is easier to prove than a tight upper bound, let alone upper and lower bounds.

Some algorithm's runtime can't be given with the same function as upper/lower bound. E.g. simple sorting algorithms are $O(n^2)$, but have lower bound $\Omega(n)$.

Some insist of striving to give performance in asymptotic terms via $\sim$, where $f(n) \sim g(n)$ if

$$\lim_{n \to \infty} \frac{f(n)}{g(n)} = 1$$

(say as an average, or worst case, in term of number of some critical operation, such as comparisons when sorting). I.e., wiggle room, but no (possibly humongous) constants swept under the rug.

$\endgroup$
  • $\begingroup$ When we refer to "runtime", we refer to something like best-case running time, worst-case running time and average-case running time. Eg: Quicksort has $\Theta(n^2)$ worst case running time and $\Theta(n)$ best case running time. Asymptotics are defined on functions right. $\endgroup$ – iart Feb 24 '16 at 21:20
1
$\begingroup$

If big-Theta can be used in place of big-Oh, it should be used unless it adds unnecessary difficulty for understanding. There are some subtle cases when big-Theta cannot be used in place of big-Oh, e.g.:

Consider the following problem: sort arrays of even length. The program to solve this problem could be: if array length is odd exit immediately, if array length is even do bubble sort. What's the worst-case running time of this algorithm?

It is surely $O(n^2)$, but it is NOT $\Omega(n^2)$ in the sense $\Omega$ is usually defined. Instead, its worst-case running time is "$\Omega(n^2)$ infinitely often" so to speak (warning: non-standard terminology).

$\endgroup$
0
$\begingroup$

In the reply of "why do algorithm books use big-Oh and not Theta":

Big-Oh is used for the worst case analysis and Big-Omega is used for best case only. But analyzing in terms of Big-Theta, we talk about both Big-Oh & Big-Omega simultaneously.

ie. For Big-Theta it is necessary that Big-Oh == Big-Omega , otherwise we can't talk about Big-Theta.

So, where ever(book/any doc) you see the use of Big-Theta , they are giving the complexity of both Big-Oh & Big-Omega(and both are equal too). But many cases they are not equal then we only use Big-Oh just for worst case.

$\endgroup$

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.