In this lecture, we'll continue our formal treatment of acentotic notation. We've
already discussed big O notation, which is by far the most important and ubiquitous
concept that's part of acentotic notation, but, for completeness, I do wanna tell you
about a couple of close relatives of big O, namely omega and theta. If big O is
analogous to less than or equal to, then omega and theta are analogous to greater
than or equal to, and equal to, respectively. But let's treat them a
little more precisely. The formal definition of omega notation closely
mirrors that of big O notation. We say that one function, t of n, is big omega of
another function. Function F. Of N. If eventually that is for sufficiently large
N. It's lower bounded by constant multiple of F. Of N. And we quantify the ideas of a
constant multiple and eventually in exactly the same way as before, namely via
explicitly giving two constants a C and M knot. Such that T of N is bounded below by
C times F of N for all sufficiently large N. That is, for all N at least N knot.
There's a picture just like there was for big O notation. Perhaps we have a function
T of N which looks something like this green curve. And then we have another
function F of N which is above T of N. But then when we multiply F of N by one half,
we get something that, eventually, is always below T of N. So in this picture,
this is an example where T of N is indeed big Omega of F of N. As far as what the
constants are, well, the multiple that we use, C, is obviously just one half. That's
what we're multiplying F of N by. And as [inaudible] before, and not as the
crossing point between the two functions. So, and not is the point after which C
times F [inaudible] lies below T of N forevermore. So that's Big Omega. The
fifth invitation is the equivalent of equals, and so it just means that the
function is both Big O of F of N and Omega of F of N. An equivalent way to think
about this is that eventually, T of N is sandwiched between two different constant
multiples of F of N. I'll write that down, and I'll leave it to you to verify that
the two notions were equivalent. That is, one implies the other and vice versa. So
what do I mean by T of N is eventually sandwiched between to multiples of F of N,
[inaudible] two constants. A small one, C1, and a big constant C2, and for all N
at least, and not. T of N lies between those two
constant multiples. The next quiz is meant to check your understanding
of these three concepts. Big O, Big Omega and Big Theta notiation. So the final
three responses are all correct. And I hope the high level intuition for why is
fairly clear. T of N is definitely a quadratic function. We know that the
linear term doesn't matter much as it grows, as N grows large. So since it has
quadratic growth, then the third response should be correct. It's theta of N
squared. And it is omega of N. So Omega event is not a very good lower bound on
the [inaudible] rate of growth of T of N, but it is legitimate. Indeed, as a
quadratic [inaudible] function, it grows at least as fast as a linear function. So
it's Omego of N. For the same reason, big O and cubed, it's not a very good upper
bound, but it is a legitimate one, it is correct. The rate of growth of T of N is
at most cubic. In fact, it's the most quadratic, but it is indeed, at most,
cubic. Now if you wanted to prove these three statements formally, you would just
exhibit the appropriate constants. So for proving that it's big Omega of N,
[inaudible]. Take n not equal to one, and c equal to one-half. For the final
statement, again you could take N not equal to one. And C equal to say four. And
to prove that it's theta of N squared you could do something similar just using he
two constants combined. So N naught would be one. You take C1 to be one-half an C2
to be four. And I'll leave it to you to verity that the formal definitions of big
omega, big theta, and big O would be satisfied with these choices of constants.
One final piece of ancentotic notation, we're are not going to use this much, but
you do see it from time to time so I wanted to mention it briefly. This is
called little O notation, in contrast to big O notation. So while big O notation
informally is a less than or equal to type relation, little O is a strictly less than
relation. So intuitively it means that one function is growing strictly less quickly
than another. So formally we say that a function T of N is a little low of F of N.
If and only if for all constancy. There is a constant N knot beyond which T of N is
upper bounded by this constant multiple C times by F M N. So the difference between
this definition and that [inaudible], is that, to prove that one function is bigger
[inaudible] another, we only have to exhibit one measly constant C, such that C
times F of F, F of N, is, upper bound, eventually, for T of N. By contrast, to
prove that something is a little low of another function, we have to prove
something quite a bit stronger. We have to prove that, for every single constant C,
no matter how small, for every C, there exists some large enough and not beyond
which T of N is bounded above by C times F of N. So, for those of you looking for a
little more facility with little or notation, I'll leave it as an exercise to
prove that. As you'd expect for all [inaudible] powers K, in fact, N to the K
minus one Is little O of N to the K. There is an analogous notion of little omega
notation expressing that one function grows strictly quicker than another. But
that one you don't see very often, and I'm not gonna say anything more about it. So
let me conclude this video with a quote from an article, back from 1976, about my
colleague Don Knuth, widely regarded as the grandfather of the formal analysis of
algorithms. And it's rare that you can pinpoint why and where some kind of
notation became universally adopted in the field. In the case of asymptotic notation
in. Indeed, it's very clear where it came from. The notation was not invented by
algorithm designers or computer scientists. It's been in use in number
theories since the nineteenth century. But it was [inaudible] in'76 that proposed
that this become the standard language for discussing [inaudible], rate of growth,
and in particular, for the running time of algorithms. So in particular, he says in
this article, on the basis of the issues discussed here, I propose that members of
[inaudible] Act, this is the special interest group of the ACM, which is
concerned with, theoretical computer science in particular, the analysis of
algorithms. So I propose that the members of SIGACT and editors in computer science
and mathematics journals adopt the O, omega, and theta notations as defined
above unless a better alternative can be found reasonably soon. So clearly a better
alternative was not found and ever since that time this has been the standard way
of discussing the rate of growth of running times of algorithms and that's
what we'll be using here.