0:00:00.034,0:00:03.033
In the following series of videos, we'll[br]give a formal treatment of asymptotic

0:00:03.033,0:00:08.053
notation, in particular big O notation, as[br]well as work through a number of examples.

0:00:08.053,0:00:12.049
Big O notation concerns functions defined[br]on the positive integers, we'll call it t

0:00:12.049,0:00:16.699
of n. We'll pretty much always have the[br]same semantics for t of n. We're gonna be

0:00:16.699,0:00:20.038
concerned about the worst-case running[br]time of an algorithm, as a function of the

0:00:20.038,0:00:24.091
input size, n. So, the question I wanna[br]answer for you in the rest of this video,

0:00:24.091,0:00:29.068
is, what does it mean when we say a[br]function, t of n, is big O of f of n. Or

0:00:29.068,0:00:34.068
hear f of n is some basic function, like[br]for example n log n. So I'll give you a

0:00:34.068,0:00:38.037
number of answers, a number of ways of, to[br]think about what big O notation really

0:00:38.037,0:00:42.029
means. For starters let's begin with an[br]English definition. What does it mean for

0:00:42.029,0:00:46.053
a function to be big O of F of N? It means[br]eventually, for all sufficiently large

0:00:46.053,0:00:51.579
values of N, it's bounded above by a[br]constant multiple of F of N. Let's think

0:00:51.579,0:00:55.489
about it in a couple other ways. So next[br]I'm gonna translate this English

0:00:55.489,0:01:00.034
definition into picture and then I'll[br]translate it into formal mathematics. So

0:01:00.034,0:01:05.039
pictorially you can imagine that perhaps[br]we have [inaudible] denoted by this blue

0:01:05.039,0:01:11.035
functions here. And perhaps F of N is[br]denoted by this green function here, which

0:01:11.035,0:01:16.679
lies below T of N. But when we double F of[br]N, we get a function that eventually

0:01:16.679,0:01:21.063
crosses T of N and forevermore is larger[br]than it. So in this event, we would say

0:01:21.063,0:01:27.009
that T event indeed is Big O of F event.[br]The reason being that for all sufficiently

0:01:27.009,0:01:31.729
large, and once we go far enough out right[br]on this graph, indeed, the constant

0:01:31.729,0:01:36.279
multiple times F [inaudible] twice[br][inaudible], is an upper bound on T event.

0:01:36.279,0:01:39.074
So finally, let me give you a actual[br]mathematical definition that you could use

0:01:39.074,0:01:44.279
to do formal proofs. So how do we say, in[br]mathematics, that eventually it should be

0:01:44.279,0:01:48.063
bounded above by a constant multiple of F[br]event? We see that there exists two

0:01:48.063,0:01:55.739
constants, which I'll call c and n not. So[br]that t of n is no more than C times F of

0:01:55.739,0:02:02.139
N, for all n that exceed or equal and not.[br]So, the role of these two constants is to

0:02:02.139,0:02:05.279
quantify what we mean by a constant[br]multiple, and what we mean by sufficiently

0:02:05.279,0:02:09.056
large, in the English definition. C[br]obviously quantifies the constant multiple

0:02:09.056,0:02:13.489
of f of n, and n knot is quantifying[br]sufficiently large, that's the threshold

0:02:13.489,0:02:19.093
beyond which we insist that, c times f of[br]n is an upper-bound on t of n. So, going

0:02:19.093,0:02:25.159
back to the picture, what are c and n[br]knot? Well, c, of course, is just going to

0:02:25.159,0:02:30.409
be two. And N. Knot is the crossing point.[br]So we get to where two F. Of N. And T. Of

0:02:30.409,0:02:36.062
N. Cross, and then we drop the acentode.[br]This would be the relative value. Of N not

0:02:36.062,0:02:39.879
in this picture, so that's the formal[br]definition, the way to prove that

0:02:39.879,0:02:43.769
something's bigger than [inaudible] you[br]exhibit these two constants C and N not

0:02:43.769,0:02:48.075
and it better be the case that for all N[br]not C times F of N upper-bounds T of N.

0:02:48.075,0:02:52.003
One way to think about it if you're trying[br]to establish that something is big O of

0:02:52.003,0:02:55.739
some function it's like you're playing a[br]game against an opponent and you want to

0:02:55.739,0:03:00.018
prove that. This inequality here holds and[br]your opponent must show that it doesn't

0:03:00.018,0:03:05.159
hold for sufficiently large N you have to[br]go first your job is to pick a strategy in

0:03:05.159,0:03:08.969
the form of a constant C and a constant N[br]not and your opponent is then allowed to

0:03:08.969,0:03:14.045
pick any number N larger than N not so the[br]function is [inaudible] if and only if you

0:03:14.045,0:03:18.078
have a winning strategy in this game. If[br]you can up front commit to constants C and

0:03:18.078,0:03:23.239
N not so that no matter how big of an N[br]your opponent picks, this inequality holds

0:03:23.239,0:03:26.819
if you have no winning strategy then it's[br]not to go of F of N no matter what C of N

0:03:26.819,0:03:30.819
not you choose your opponent can always[br]flip this in equality. By choosing a

0:03:30.819,0:03:35.056
suitable, suitable large value of N. I[br]want to emphasis one last thing which is

0:03:35.056,0:03:40.739
that these constants, what do I mean by[br]constants. I mean they are independent of

0:03:40.739,0:03:45.003
N. And so when you apply this definition,[br]and you choose your constant C [inaudible]

0:03:45.003,0:03:48.639
not, it better be that N does not appear[br]anywhere. So C should just be something

0:03:48.639,0:03:53.549
like a thousand or a million. Some[br]constant independent of N. So those are a

0:03:53.549,0:03:57.319
bunch of way to think about [inaudible][br]notation. In English, you wanna have it

0:03:57.319,0:04:00.609
bound above for sufficiently large numbers[br]N. I'm showing you how to translate that

0:04:00.609,0:04:04.109
into mathematics that give you a pictorial[br]representation. And also sort of a game

0:04:04.109,0:04:07.059
theoretic way to think about it. Now,[br]let's move on to a video that explores a

0:04:07.059,9:59:59.000
number of examples.