What is the difference between O, Ω, and Θ?_问答_开发者

I am learning algorithm analysis. I am having trouble understanding the difference between O, Ω, and Θ.

The way they're defined is as follows:

f(n) = O(g(n)) means c · g(n) is an upper bound on f(n). Thus there exists some constant c such that f(n) is always ≤ c · g(n), for large enough n (i.e., n ≥ n0 for some constant n0).

f(n) = Ω(g(n)) means c · g(n) is a lower bound on f(n). Thus there exists some constant c such that f(n) is always ≥ c · g(n), for all n ≥ n0.

f(n) = Θ(g(n)) means c1 · g(n) is an upper bound on f(n) and c2 · g(n) is a lower bound on f(n), for all n ≥ n0. Thus there exist constants c1 and c2 such that f(n) ≤ c1 ·g(n) and f(n) ≥ c2 ·g(n). 开发者_开发问答This means that g(n) provides a nice, tight bound on f(n).

The way I have understood this is:

O(f(n)) gives worst case complexity of given function/algorithm.
Ω(f(n)) gives best case complexity of given function/algorithm.
Θ(f(n)) gives average case complexity of given function/algorithm.

Please correct me if I am wrong. If it is the case, time complexity of each algorithm must be expressed in all three notations. But I observed that it's expressed as either O, Ω, or Θ; why not all three?

It is important to remember that the notation, whether O, Ω or Θ, expresses the asymptotic growth of a function; it does not have anything intrinsically to do with algorithms per se. The function in question may be the "complexity" (running time) of an algorithm, either worst-case, best-case or average-case, but the notation is independent of where the function comes from.

For example, the function f(n)=3n²+5 is:

O(n²), it is also O(n²log n), O(n³), O(n⁴) and so on, but is not O(n).
Ω(n²), it is also Ω(n log n), Ω(n) and so on, but is not Ω(n³).
Θ(n²). It is not even Θ(n²log n) or Θ(n²/log n).

Now, usually the function considered is the worst-case complexity of an algorithm, and which notation of the three is used depends on what we want to say about it and on how carefully we do the analysis. For example, we may observe that because there are two nested loops, the worst-case running time is at most O(n²), without caring about whether this is actually achieved for some input. (Usually it is obvious that it is.) Or, we may say that the worst-case running time of sorting is Ω(n log n), because there must be some inputs for which it must take at least cn(log n) steps. Or, we may look at a particular mergesort algorithm, and see that it takes at most O(n log n) steps in the worst-case and that some input makes it take n log n steps, so the worst-case running time is Θ(n log n).

Note that in all the three examples above, it was still the same (worst-case) running time that was being analyzed. We may analyze the best-case or average-case instead, but again, which notation of the three we use depends on what we want to say — whether we want to give an upper bound, lower bound, or tight bound on the order of growth of the same function.

Θ denotes an asymptotically tight upper and lower bound.

O denotes an upper bound, but this bound might or might not be tight.
o denotes an upper bound that is not tight.

Ω denotes a lower bound, but this bound might or might not be tight.
ω denotes a lower bound that is not tight.

For what those three mean, see Can Berk Güder's answer.

Note also that they have nothing at all to do with best case, worst case, and average case. Bubble sort for example is Θ(n) best case (because if the data is already sorted, only n-1 comparisons are needed), and Θ(n^2) worst case. It's Θ(n^2) average-case assuming randomly-shuffled input. That average case therefore is also O(n^2), and O(n^3), and O(2^n).

So, O, Θ and Ω tell you what kind of bound it is. They don't tell you what the bound is a limit on. In context, it might be a limit on the best case, the worse case, the average case, or the algorithm as a whole (all cases).

Of course if an algorithm has Ω(g) best case, then it is itself Ω(g). If it has O(g) worst case it is O(g). So there is a relation there. But if it has Θ(g) average case, that tells you almost nothing about the best and worst cases.

As for "why not all three?".

If your function is Θ(g), then it is also O(g) and Ω(g). So there's not much point providing other bounds alongside a Θ bound.

When you see one of the others alone, it's generally because we only care about an upper bound, or we only care about a lower bound. So we say that all comparison sorts are necessarily Ω(n log n) worst case, and that bubble sort is O(n^2) worst case but O(n) best case, because we aren't trying to fully describe the time complexity, we're just expressing the bounds we care about in a particular context.

And in any case most people seem to be lazy, and don't want to have to type Greek letters. I know I am. So we just say that comparison sorts are "at best O(n log n)". It's an abuse of notation really, but it gets the point across.

These are some of the resources that will really help you:

Wikipedia
Wiki book
MIT Lecture Video
Video from IITB, India

Big-O notation is often referred to as complexity of an algorithm because it assures us, that the algorithm will not perform substantially more worse for large n. However, as was rightly pointed out earlier, the Big-O gives us the asymptotic evaluation and our algorithm may behave differently when certain input is given. For example quick sort can be O(n^2), when the array is already sorted. OTOH, asymptotic situation may be improved in practice with neat implementation.

Best case is represented by Ω(n) notation. Worst case is represented by Ο(n) notation. Average case is represented by Θ(n) notation.