25

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.

tskuzzy
  • 732
  • 1
  • 7
  • 12
  • 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 08 '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

2 Answers2

27

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:

Community
  • 1
Falcon
  • 19,248
  • 4
  • 78
  • 93
  • 8
    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 08 '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 08 '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 08 '11 at 12:32
9

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.

MSalters
  • 8,692
  • 1
  • 20
  • 32
  • 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 08 '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 08 '11 at 13:02