-
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.
