Big Oh vs Big Theta

Question

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

Answer 1

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.

Answer 2

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.

Answer 3

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

Answer 4

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.