24

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.

3
  • 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, 2011 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, 2011 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, 2015 at 21:01

2 Answers 2

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:

3
  • 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 8, 2011 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, 2011 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, 2011 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.

2
  • 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, 2011 at 12:45
  • 5
    @tskuzzy, take quicksort. It doesn't have a Theta-bound, because it's O(n^2) and Omega(n). Aug 8, 2011 at 13:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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