# Why is Big O taught instead of Big Theta?

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.

-
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
@jsternberg Technically you are correct. This is also true, but meaningless: "Quicksort in any case(worst, best, ...) is O(n^100). But I agree with OP it should be more accurately : QuickSort worst-case is Theta(N^2), QuickSort best-case is Theta(NlogN). Because in each case we will get different function. – Eldar Jan 16 '15 at 21:01

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.