Alex Rivera | Logout

Big-oh vs big-theta

Asked 2010-07-12T16:13:07.820
119

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?

algorithm complexity-theory
Edit
Report

1 Answer

0

I have seen Big Theta, and I'm pretty sure I was taught the difference in school. I had to look it up though. This is what Wikipedia says:

Big O is the most commonly used asymptotic notation for comparing functions, although in many cases Big O may be replaced with Big Theta Θ for asymptotically tighter bounds.

Source: Big O Notation#Related asymptotic notation

I don't know why people use Big-O when talking formally. Maybe it's because most people are more familiar with Big-O than Big-Theta? I had forgotten that Big-Theta even existed until you reminded me. Although now that my memory is refreshed, I may end up using it in conversation. :)

answered 2010-07-12T16:16:19.253

Your Answer