Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

Big O notation provides an upper bound to a function whereas Big Theta provides a tight bound. However I find that Big O notation is typically (and informally) taught and used when they really mean Big Theta.

e.g. "Quicksort is O(N^2)" can turned into the much stronger statement "Quicksort is Θ(N^2)"

While usage of Big O is technically correct, wouldn't a more prevalent use of Big Theta be more expressive and lead to less confusion? Is there some historical reason why this Big O is more commonly used?

Wikipedia notes:

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.

share|improve this question
3  
I know this doesn't really pertain to the question, but quicksort isn't theta(N^2). It's O(N^2). –  jsternberg Aug 8 '11 at 15:11
    
Big O is what the beginners/non-CS folks need to know. Big Theta is what is covered in an intro to algorithms, which will not be taken by every major. Those who have had an algorithms class can read into the Big O notation deeper if they wish. I am not sure what the Wikipedia quote refers to. With academic publications you will get your throat slit at a conference if you confuse Big O and big Theta. Some people spend their whole life chasing the Theta and those are HARD HARD problems. –  Job Sep 24 '11 at 14:50
add comment

2 Answers 2

Because you are usually just interested in the worst case when analyzing the performance. Thus, knowing the upper bound is sufficient.

When it runs faster than expected for a given input - that is ok, it's not the critical point. It's mostly negligible information.

Some algorithms, as @Peter Taylor noted, don't have a tight bound at all. See quicksort for example which is O(n^2) and Omega(n).

Moreover, tight bounds are often more difficult to compute.

See also:

share|improve this answer
3  
But Big O doesn't necessarily correspond to worst case performance. I could say quicksort runs in O(2^n) and be 100% correct. It would be much more meaningful if I say algorithm X runs in Theta(N^2) rather than O(N^2). –  tskuzzy Aug 8 '11 at 12:18
    
Also, tight bounds are almost always computed when analyzing algorithms rather than just an upper bound. I'm asking why people don't just use the much more expressive theta notation when they can. –  tskuzzy Aug 8 '11 at 12:24
9  
I told you why most programmers don't use it. We are lazy and don't need as much accuracy. Nobody stops you from using big theta if you want. Go ahead, do it. Your algorithm-choice will most likely not benefit that much from it. I've never heard of a programmer confused by the big O notation. I, too, don't find it confusing at all. –  Falcon Aug 8 '11 at 12:32
add comment

One reason is that there are many cases in which Θ just isn't known. For instance, Matrix multiplication is O(n^2.376) but there's no known tight bound. Sure, as far as I can tell, there is a tight bound for Matrix multiplication, but we don't know its value.

share|improve this answer
    
But that would be the bounds for the running time of a problem, not a particular algorithm. While matrix multiplication in general can be solved faster than cubic time, the naive algorithm is Θ(n^3) no matter what. –  tskuzzy Aug 8 '11 at 12:45
5  
@tskuzzy, take quicksort. It doesn't have a Theta-bound, because it's O(n^2) and Omega(n). –  Peter Taylor Aug 8 '11 at 13:02
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.