In the following series of videos, we'll give a formal treatment of asymptotic
notation, in particular big O notation, as well as work through a number of examples.
Big O notation concerns functions defined on the positive integers, we'll call it t
of n.
We'll pretty much always have the same semantics for t of n.
We're gonna be concerned about the worst-case running
time of an algorithm, as a function of the input size, n.
So, the question I wanna answer for you in the rest of this video,
is, what does it mean when we say a function, t of n, is big O of f of n.
Or hear f of n is some basic function, like
for example n log n.
So I'll give you a number of answers, a number of ways of, to
think about what big O notation really means.
For starters let's begin with an English definition.
What does it mean for a function to be big O of F of N?
It means eventually, for all sufficiently large
values of N, it's bounded above by a constant multiple of F of N. Let's think
about it in a couple other ways.
So next I'm gonna translate this English
definition into picture and then I'll translate it into formal mathematics.
So pictorially you can imagine that perhaps
we have [inaudible] denoted by this blue functions here.
And perhaps F of N is denoted by this green function here, which
lies below T of N. But when we double F of N, we get a function that eventually
crosses T of N and forevermore is larger than it.
So in this event, we would say that T event indeed is Big O of F event.
The reason being that for all sufficiently large, and once we go far enough out right
on this graph, indeed, the constant multiple times F [inaudible] twice
[inaudible], is an upper bound on T event.
So finally, let me give you a actual mathematical definition that you could use
to do formal proofs.
So how do we say, in mathematics, that eventually it should be
bounded above by a constant multiple of F event?
We see that there exists two constants, which I'll call c and n not.
So that t of n is no more than C times F of
N, for all n that exceed or equal and not.
So, the role of these two constants is to quantify what we mean by a constant
multiple, and what we mean by sufficiently large, in the English definition.
C obviously quantifies the constant multiple
of f of n, and n knot is quantifying sufficiently large, that's the threshold
beyond which we insist that, c times f of n is an upper-bound on t of n.
So, going back to the picture, what are c and n
knot?
Well, c, of course, is just going to be two.
And N. Knot is the crossing point.
So we get to where two F. Of N. And T. Of N. Cross, and then we drop the acentode.
This would be the relative value.
Of N not in this picture, so that's the formal
definition, the way to prove that something's bigger than [inaudible] you
exhibit these two constants C and N not and it better be the case that for all N
not C times F of N upper-bounds T of N. One way to think about it if you're trying
to establish that something is big O of some function it's like you're playing a
game against an opponent and you want to prove that.
This inequality here holds and your opponent must show that it doesn't
hold for sufficiently large N you have to go first your job is to pick a strategy in
the form of a constant C and a constant N not and your opponent is then allowed to
pick any number N larger than N not so the function is [inaudible] if and only if you
have a winning strategy in this game.
If you can up front commit to constants C and
N not so that no matter how big of an N your opponent picks, this inequality holds
if you have no winning strategy then it's not to go of F of N no matter what C of N
not you choose your opponent can always flip this in equality.
By choosing a suitable, suitable large value of N. I
want to emphasis one last thing which is that these constants, what do I mean by
constants.
I mean they are independent of N. And so when you apply this definition,
and you choose your constant C [inaudible] not, it better be that N does not appear
anywhere.
So C should just be something like a thousand or a million.
Some constant independent of N. So those are a
bunch of way to think about [inaudible] notation.
In English, you wanna have it bound above for sufficiently large numbers
N. I'm showing you how to translate that into mathematics that give you a pictorial
representation.
And also sort of a game theoretic way to think about it.
Now, let's move on to a video that explores a
number of examples.