Original subtitles

We have seen Big Theta as the notation for actual complexity, and Big O for worst-case complexity.

Similarly, as these two, Big Omega is a notation for the best-case complexity, so consider this graph.

This could be a graph of the logarithm, and consider the area above the curve.

Then we have a lower bound for another function, if that function stays above our curve from a certain point,

just like in this example. By the way, the lower bound here in this example is not tight, so even though it

is correct formally, it may actually not say anything useful about the function.

Let's skip quickly to the formal definition. Dimmed out here on the slide is the definition of Big O.

I modified it slightly so you can see how similar Big Omega is to Big O.

The first part is the same. We need a function f, and another function g to be used as lower bound.

The constant part is almost the same, but the function should be larger than g, but smaller than g.

The small n constant is the same, and again, instead of having f being smaller than g, it should be larger.

If this is true, then f is not Big O of g of N, but Big Omega of g of N.

So the best case of the two versions of the search algorithm we have seen was if it found the needle in the

first element of the haystack. And here we only need to perform some constant number of instructions that

gives a best case complexity of Big Omega of 1. In comparison, the loop that iterated through all values of

N, and which had a worst-case complexity of Big O of N, also had a best-case complexity of Big Omega of N,

because it can never finish before having looked through all N values.

And the pair generation example with the worst-case complexity of Big O of N squared had a best-case

complexity of Big Omega of N squared, because its termination could never happen before having looked through

all N times N values.