Would you like to inspect the original subtitles? These are the user uploaded subtitles that are being translated:
0
00:00:01,500 --> 00:00:10,500
We have seen Big Theta as the notation for actual complexity, and Big O for worst-case complexity.
1
00:00:10,500 --> 00:00:18,500
Similarly, as these two, Big Omega is a notation for the best-case complexity, so consider this graph.
2
00:00:18,500 --> 00:00:26,068
This could be a graph of the logarithm, and consider the area above the curve.
3
00:00:26,068 --> 00:00:35,067
Then we have a lower bound for another function, if that function stays above our curve from a certain point,
4
00:00:35,067 --> 00:00:43,067
just like in this example. By the way, the lower bound here in this example is not tight, so even though it
5
00:00:43,067 --> 00:00:49,067
is correct formally, it may actually not say anything useful about the function.
6
00:00:49,067 --> 00:00:57,500
Let's skip quickly to the formal definition. Dimmed out here on the slide is the definition of Big O.
7
00:00:57,500 --> 00:01:02,067
I modified it slightly so you can see how similar Big Omega is to Big O.
8
00:01:02,067 --> 00:01:12,067
The first part is the same. We need a function f, and another function g to be used as lower bound.
9
00:01:12,067 --> 00:01:20,067
The constant part is almost the same, but the function should be larger than g, but smaller than g.
10
00:01:20,067 --> 00:01:31,067
The small n constant is the same, and again, instead of having f being smaller than g, it should be larger.
11
00:01:31,067 --> 00:01:40,067
If this is true, then f is not Big O of g of N, but Big Omega of g of N.
12
00:01:40,067 --> 00:01:46,067
So the best case of the two versions of the search algorithm we have seen was if it found the needle in the
13
00:01:46,067 --> 00:01:53,067
first element of the haystack. And here we only need to perform some constant number of instructions that
14
00:01:53,067 --> 00:02:02,067
gives a best case complexity of Big Omega of 1. In comparison, the loop that iterated through all values of
15
00:02:02,067 --> 00:02:13,068
N, and which had a worst-case complexity of Big O of N, also had a best-case complexity of Big Omega of N,
16
00:02:13,068 --> 00:02:18,068
because it can never finish before having looked through all N values.
17
00:02:18,068 --> 00:02:28,068
And the pair generation example with the worst-case complexity of Big O of N squared had a best-case
18
00:02:28,068 --> 00:02:35,068
complexity of Big Omega of N squared, because its termination could never happen before having looked through
19
00:02:35,068 --> 00:02:40,000
all N times N values.
2539
Can't find what you're looking for?
Get subtitles in any language from opensubtitles.com, and translate them here.