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