[Solved]: Big Oh vs Big Theta

Problem Detail: 

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

Asked By : iart

Answered By : maybeshewill

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/53575