Big-oh vs big-theta

Question

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?

Answer 1

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³+ 22n²+ 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).

1. T(n) = O(n¹⁰⁰), which is identical to T(n) ∈ O(n¹⁰⁰)
2. T(n) = O(n³), which is identical to T(n) ∈ O(n³)
3. T(n) = Θ(n³), which is identical to T(n) ∈ Θ(n³)

The equivalent English statements are respectively:

1. T(n) grows asymptotically no faster than n¹⁰⁰
2. T(n) grows asymptotically no faster than n³
3. T(n) grows asymptotically as fast as n³.

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.