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

of N is not a very good lower bound on the asymptotic rate of growth of T of N,

but it is legitimate. Indeed, as a quadratic growing function, it grows

at least as fast as a linear function. So it's Omega of N. For the same reason, big

O of N 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 at 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, you could take N naught equal to one, and

C equal to one-half. For the final statement, again you could take N naught

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 the two constants combined. So N naught would

be one. You could take C1 to be one-half and C2 to be four. And I'll leave it to you to

verify that the formal definitions of big omega, big theta, and big O would be

satisfied with these choices of constants. One final piece of asymptotic 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 little O of F of N, if and only if for all constants C, there is

a constant N naught beyond which T of N is upper bounded by this constant multiple C

times by F of N. So the difference between this definition and that of Big-O notation, is

that, to prove that one function is big O of another, we only have to

exhibit one measly constant C, such that C times F of N is upper bound,

eventually, for T of N. By contrast, to prove that something is little O 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 N naught 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 O

notation, I'll leave it as an exercise to prove that, as you'd expect for all

polynomial 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, 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 theory since the nineteenth century. But

it was Don Knuth in '76 that proposed that this become the standard language for

discussing 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 SIGACT," 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.