Big-oh vs big-theta
algorithm, complexity-theory
Solution
Big-O is an upper bound.
Big-Theta is a tight bound, i.e. upper and lower bound.
When people only worry about what's the worst that can happen, big-O is sufficient; i.e. it says that "it can't get much worse than this". The tighter the bound the better, of course, but a tight bound isn't always easy to compute.
See also
- Wikipedia/Big O Notation
Related questions
- What is the difference between Θ(n) and O(n)?
The following quote from Wikipedia also sheds some light:
Informally, especially in computer science, the Big O notation often is permitted to be somewhat abused to describe an asymptotic tight bound where using Big Theta notation might be more factually appropriate in a given context.
For example, when considering a function `T(n) = 73n`3`+ 22n`2`+ 58`, all of the following are generally acceptable, but tightness of bound (i.e., bullets 2 and 3 below) are usually strongly preferred over laxness of bound (i.e., bullet 1 below).
- `T(n) = O(n`100`)`, which is identical to `T(n) ∈ O(n`100`)`
- `T(n) = O(n`3`)`, which is identical to `T(n) ∈ O(n`3`)`
- `T(n) = Θ(n`3`)`, which is identical to `T(n) ∈ Θ(n`3`)`
The equivalent English statements are respectively:
- `T(n)` grows asymptotically no faster than `n`100
- `T(n)` grows asymptotically no faster than `n`3
- `T(n)` grows asymptotically as fast as `n`3.
So while all three statements are true, progressively more information is contained in each. In some fields, however, the Big O notation (bullets number 2 in the lists above) would be used more commonly than the Big Theta notation (bullets number 3 in the lists above) because functions that grow more slowly are more desirable.
Problem
Possible Duplicate: What is the difference between Θ(n) and O(n)? It seems to me like when people talk about algorithm complexity informally, they talk about big-oh. But in formal situations, I often see big-theta with the occasional big-oh thrown in. I know mathematically what the difference is between the two, but in English, in what situation would using big-oh when you mean big-theta be incorrect, or vice versa (an example algorithm would be appreciated)? Bonus: why do people seemingly always use big-oh when talking informally?