1 00:00:00,000 --> 00:00:04,256 In the following series of videos, we'll give a formal treatment of asymptotic 2 00:00:04,256 --> 00:00:08,294 notation, in particular Big-Oh notation, as well as work through a number of 3 00:00:08,294 --> 00:00:10,641 examples. Big-Oh notation concerns functions 4 00:00:10,641 --> 00:00:13,588 defined on the positive integers. We'll call it T of n. 5 00:00:13,588 --> 00:00:16,862 We'll pretty much always have the same semantics for T of n. 6 00:00:16,862 --> 00:00:20,955 We're going to be concerned about the worst case running time of an algorithm 7 00:00:20,955 --> 00:00:24,939 as a function of the input size n. So the question I want to answer for you 8 00:00:24,939 --> 00:00:28,759 in the rest of this video is, what does it mean when we say a function 9 00:00:28,759 --> 00:00:32,415 T of n is Big-Oh of F of n? Where here, F of n is some basic function 10 00:00:32,415 --> 00:00:35,749 like, for example, N log N. So, I'll give you a number of answers. 11 00:00:35,749 --> 00:00:39,369 A number of ways of to think about what Big-Oh notation really means. 12 00:00:39,369 --> 00:00:42,350 But for starters, let's begin with an English definition. 13 00:00:42,350 --> 00:00:45,278 What does it mean for a function to be Big-Oh of F of n? 14 00:00:45,278 --> 00:00:48,419 It means eventually, for all sufficiently large values of n, 15 00:00:48,419 --> 00:00:51,187 it's bounded above by a constant multiple of F of n. 16 00:00:51,187 --> 00:00:53,530 Let's think about it in a couple other ways. 17 00:00:53,530 --> 00:00:57,729 So next, I'm going to translate this English definition into a picture, and 18 00:00:57,729 --> 00:01:00,509 then I'll translate it into formal mathematics. 19 00:01:00,509 --> 00:01:04,946 So pictorially, you can imagine that perhaps we have T of n denoted by this 20 00:01:04,946 --> 00:01:08,698 blue function here. And perhaps, F of n is denoted by this 21 00:01:08,698 --> 00:01:11,910 green function here which lies below T of n. 22 00:01:11,910 --> 00:01:17,385 But when we double F of n, we get a function that eventually crosses T of n 23 00:01:17,385 --> 00:01:22,379 and forever more is larger than it. So in this event, we would say that T of 24 00:01:22,379 --> 00:01:26,342 n indeed is Big-Oh of F of n. The reason being for all sufficiently 25 00:01:26,342 --> 00:01:30,855 large n, once we go out far enough right on this graph, indeed the constant 26 00:01:30,855 --> 00:01:34,696 multiple times F of n, twice F of n N is an upper bound of T of n. 27 00:01:34,696 --> 00:01:39,208 So finally, let me give you actual mathematical definition that you could 28 00:01:39,208 --> 00:01:43,050 use to give formal proofs. So, how do we say in mathematics that 29 00:01:43,050 --> 00:01:47,380 eventually it should be bounded above by a constant multiple of F of n? 30 00:01:47,380 --> 00:01:53,106 We see that there exists two constants, which I'll call c and n0. 31 00:01:53,106 --> 00:02:00,200 So that T of n is no more than c * F(n), for all n that exceed or equal n0. 32 00:02:00,200 --> 00:02:04,855 So the role of these two constants is to quantify what we mean by a constant 33 00:02:04,855 --> 00:02:09,329 multiple and what we mean by sufficiently large, in the English definition. 34 00:02:09,329 --> 00:02:13,441 c obviously quantifies the constant multiple of F of n, and n0 not is 35 00:02:13,441 --> 00:02:18,278 quantifying sufficiently large. That's the threshold beyond which we insist that 36 00:02:18,278 --> 00:02:23,296 c * F(n) is an upper bound on T of n. So, going back to the picture, what are c 37 00:02:23,296 --> 00:02:26,380 and n0? Well, c of course, is just going to be two, 38 00:02:26,380 --> 00:02:30,328 and n0 is the crossing point. So, if you look at where two F of n and T 39 00:02:30,328 --> 00:02:32,487 of n cross, and then we drop the asymptote. 40 00:02:32,487 --> 00:02:35,540 This would be the relevant value of n0 in this picture. 41 00:02:35,540 --> 00:02:39,331 So, that's the formal definition. The way to prove that something's Big-Oh 42 00:02:39,331 --> 00:02:41,963 of F of n, you would exhibit these two constants, c 43 00:02:41,963 --> 00:02:45,175 and n0. And it better be the case that for all n 44 00:02:45,175 --> 00:02:47,544 at least n0, c * F(n) upper bounds, T of n. 45 00:02:47,544 --> 00:02:51,440 One way to think about it if you're trying to establish that something is 46 00:02:51,440 --> 00:02:54,756 Big-Oh of some function, it's like you're playing a game against 47 00:02:54,756 --> 00:02:57,064 some opponent. And you want to prove that this 48 00:02:57,064 --> 00:03:01,040 inequality here holds, and your opponent want to show that it doesn't hold for 49 00:03:01,040 --> 00:03:03,946 sufficiently large n. You have to go. First, your job is to 50 00:03:03,946 --> 00:03:08,432 pick a strategy in a form of a constant c and a constant n0, and your opponent is 51 00:03:08,432 --> 00:03:11,235 then allowed to pick any number n larger then n0. 52 00:03:11,235 --> 00:03:15,211 So the function is Big-Oh of F of n if and only if you have a winning strategy 53 00:03:15,211 --> 00:03:17,964 in this game. If you can upfront commit to constants c 54 00:03:17,964 --> 00:03:22,041 and n0 so that no matter how big an n your opponent picks this inequality 55 00:03:22,041 --> 00:03:24,233 holds. If you have no winning strategy, then 56 00:03:24,233 --> 00:03:27,700 it's not Big-Oh of F of n. No matter what c and n0 you choose your 57 00:03:27,700 --> 00:03:32,959 opponent can always flip this inequality by choosing suitable, suitable large 58 00:03:32,959 --> 00:03:36,364 value of n. I want to emphasize one last thing, which 59 00:03:36,364 --> 00:03:41,326 is that these constants, what do I mean by constant? I mean, they are independent 60 00:03:41,326 --> 00:03:43,547 of n. And so, when you apply this definition 61 00:03:43,547 --> 00:03:47,459 and you choose your constant c and n0, it better be that n does not appear 62 00:03:47,459 --> 00:03:49,905 anywhere. So, c should just be something like 1,000 63 00:03:49,905 --> 00:03:52,106 or a million. Some constant independent of n. 64 00:03:52,106 --> 00:03:55,529 So, those are a bunch of ways to think about Big-Oh notation in English. 65 00:03:55,529 --> 00:03:58,659 You want to have a bound above for sufficiently large numbers n. 66 00:03:58,659 --> 00:04:02,523 I've shown you how to translate that into mathematics, I'd give you a pictorial 67 00:04:02,523 --> 00:04:05,995 representation and also a sort of game theoretic way to think about it. 68 00:04:05,995 --> 00:04:09,077 Now, let's move onto a video that explores a number of examples.