1 00:00:00,720 --> 00:00:08,610 OK, so now we are going to get back into the asymptotic analysis of algorithms, so we talked a little 2 00:00:08,610 --> 00:00:13,770 bit about this earlier on in this section of the course where we were looking at big oh and talking 3 00:00:13,770 --> 00:00:20,670 about basic operations and how to figure out the time complexity of an algorithm, the runtime complexity. 4 00:00:21,300 --> 00:00:29,010 And I did kind of foreshadow that we would be looking deeper into this matter and now that time has 5 00:00:29,010 --> 00:00:29,370 come. 6 00:00:29,940 --> 00:00:37,200 So what we're going to start out with is kind of a recap and looking at what it really means to have 7 00:00:37,200 --> 00:00:39,630 bounds and what our case is like. 8 00:00:39,630 --> 00:00:41,370 Best case, average case, worst case. 9 00:00:41,730 --> 00:00:42,990 So let's go ahead and get started. 10 00:00:44,460 --> 00:00:47,010 So a quick reminder for taking a step back. 11 00:00:47,010 --> 00:00:51,180 Let's remember what we talk about when we're talking about doing asymptotic analysis on algorithms. 12 00:00:51,180 --> 00:00:57,300 So the real question that we ask is what is happening to our number of operations and our function as 13 00:00:57,480 --> 00:01:00,510 the input to our function gets larger and larger? 14 00:01:00,540 --> 00:01:06,030 So what is the output of the function to be, how many basic operations are happening based on the input 15 00:01:06,030 --> 00:01:06,630 that we have? 16 00:01:07,350 --> 00:01:09,360 So here you just see a graph over on the right. 17 00:01:10,350 --> 00:01:13,080 Going to use that in the next few slides as well. 18 00:01:13,680 --> 00:01:17,610 So to the right, we have these two functions here. 19 00:01:17,910 --> 00:01:21,240 And of course, remember that are in this the size of our input. 20 00:01:21,240 --> 00:01:24,060 That's the x axis y axis is the output. 21 00:01:24,060 --> 00:01:31,590 So the number of operations based on that in Big O is representative of what we call an upper bound 22 00:01:31,590 --> 00:01:35,350 for the function that is the red line in the picture. 23 00:01:36,650 --> 00:01:43,970 So we could say that big of an squared is a bounding function of f of T in here. 24 00:01:44,600 --> 00:01:45,620 An upper bound. 25 00:01:46,340 --> 00:01:51,440 So what is the upper bound really mean and why we've been using Bigo? 26 00:01:51,440 --> 00:01:53,440 So the industry uses Bigo a lot. 27 00:01:53,450 --> 00:01:59,240 They kind of just default to that notation rather than looking into exact balance really that often. 28 00:01:59,450 --> 00:02:01,700 That's something we will look at later in the slideshow. 29 00:02:01,700 --> 00:02:05,690 But there's a difference between talking about an upper bound in an exact bound. 30 00:02:06,590 --> 00:02:13,190 So what's really meant by Bigo is that you were able to say bego of something if that something which 31 00:02:13,190 --> 00:02:14,220 is a function in there. 32 00:02:14,240 --> 00:02:18,380 So you can see if that function can be multiplied by some constants. 33 00:02:18,380 --> 00:02:23,120 So like just a number, you know, an integer like two or twenty, or it doesn't have to be an issue, 34 00:02:23,120 --> 00:02:28,880 but like a whole number or something, but just some constant if it can be multiplied by some constant 35 00:02:28,880 --> 00:02:31,820 and it's always a greater than or equal to. 36 00:02:32,940 --> 00:02:39,390 The function in question, which is the red line, then we can say that that is accurate as accurate 37 00:02:39,390 --> 00:02:42,060 statement, we can say big of something. 38 00:02:42,270 --> 00:02:47,610 If that is the case, we can multiply it by some constant and it will always be greater than or equal 39 00:02:47,610 --> 00:02:48,360 to the red line. 40 00:02:49,590 --> 00:02:54,030 For and that is for any value of and so anywhere along the x axis there. 41 00:02:55,570 --> 00:02:57,100 So let's take a closer look at that. 42 00:02:58,030 --> 00:02:59,950 Here we've zoomed in a little bit. 43 00:03:00,250 --> 00:03:03,010 So same graph, but I'm zoomed in on the beginning. 44 00:03:03,790 --> 00:03:10,420 You can see that the red line function is actually greater than what we are claiming to have be an upper 45 00:03:10,420 --> 00:03:10,780 bound. 46 00:03:10,790 --> 00:03:13,240 So the blue line is not later than it. 47 00:03:13,270 --> 00:03:17,980 The Red Line is greater than up until about an equals 20 there. 48 00:03:19,480 --> 00:03:27,430 So if we go ahead and do what we said in the previous slide and we pick some kind of constant and multiply 49 00:03:27,430 --> 00:03:28,510 it, let's see what happens. 50 00:03:28,960 --> 00:03:30,590 So we multiply it by some constant. 51 00:03:30,610 --> 00:03:37,690 I chose 20 in this picture and you can see that when we zoom in extra close, the blue line bounding 52 00:03:37,690 --> 00:03:44,950 function is always greater than or equal to the line, the red line there for any given value of in. 53 00:03:44,980 --> 00:03:49,600 So the Red Line is never going to cross above the blue line. 54 00:03:49,600 --> 00:03:54,910 And because that is the case that we were able to achieve this by multiplying by some constant. 55 00:03:55,270 --> 00:04:05,200 We can say that the blue line is bounding our function and our function is bounded by Bigo of N squared. 56 00:04:05,260 --> 00:04:06,670 So that line is then squared. 57 00:04:06,670 --> 00:04:13,270 And we can say, since it's an upper bound, we are calling it o of in squared because we use the term 58 00:04:13,270 --> 00:04:15,250 big o for the upper bound. 59 00:04:16,400 --> 00:04:18,230 So that is what Big O means. 60 00:04:20,790 --> 00:04:23,460 So let's just see if we can try something else. 61 00:04:23,910 --> 00:04:29,430 Maybe we want to say, Hey, this blue line over here, I want to multiply it by some constant and bound 62 00:04:29,430 --> 00:04:31,800 the red line, you know, have it be an upper bound? 63 00:04:32,980 --> 00:04:33,880 Of the red line. 64 00:04:34,180 --> 00:04:39,520 So right now, it's not working, let's just multiply it by a number, maybe like a hundred and maybe 65 00:04:39,520 --> 00:04:41,440 OK, now maybe is not enough. 66 00:04:41,440 --> 00:04:43,960 We see it still crosses under the red line somewhere. 67 00:04:43,960 --> 00:04:48,160 So let's do it by like 100 billion, something that for sure would never. 68 00:04:49,320 --> 00:04:53,970 You know, go below the red line, but the thing is, is that it will go below the red line. 69 00:04:54,210 --> 00:04:56,430 It's some value of in. 70 00:04:57,030 --> 00:05:04,690 This log in graph will actually go under the red line, no matter what constant we multiply it by. 71 00:05:04,710 --> 00:05:11,970 So we will always be able to find some value in in which the red line will cross above the blue line. 72 00:05:11,970 --> 00:05:21,810 And so we are unable to say that that the blue line, which is the log in, is able to be an upper bound. 73 00:05:21,810 --> 00:05:27,870 So we cannot say Bigo of log in for our function. 74 00:05:27,870 --> 00:05:30,720 We cannot say it's bounded by log in. 75 00:05:30,720 --> 00:05:33,000 The Red Line cannot be up or bounded by it. 76 00:05:33,450 --> 00:05:40,080 It can be bounded, but it cannot be up or bounded by this graph here at the log in. 77 00:05:41,040 --> 00:05:47,040 So since we can't do that, let's look into lower bounds. 78 00:05:47,640 --> 00:05:53,970 So the same way we did upper bounds, we can also find lower bound. 79 00:05:55,340 --> 00:05:59,150 And that is denoted with Big Omega rather than big. 80 00:06:00,650 --> 00:06:07,760 So here I've kind of switched the gas up and you can see that there is big omega of in on this line 81 00:06:07,760 --> 00:06:08,000 there. 82 00:06:08,000 --> 00:06:15,080 So we have a graph in and then we and that's in blue and then we have a graph which is n squared and 83 00:06:15,080 --> 00:06:16,430 that is in red. 84 00:06:17,300 --> 00:06:27,800 So we are able to call in a lower bound of the function in squared because it'll always have a slower 85 00:06:27,800 --> 00:06:30,170 or equal growth rate than the Red Line. 86 00:06:30,170 --> 00:06:35,630 So that's just like the upper bound we can find if we're able to find some kind of constant to multiply 87 00:06:35,870 --> 00:06:41,720 the blue line function by to ensure that it's always less than an equal to, we are able to accept it 88 00:06:41,720 --> 00:06:45,980 as being called a lower bound in which we would use that symbol. 89 00:06:46,010 --> 00:06:52,280 Big Omega So we'd say it is lower bounded by Big Omega of in there. 90 00:06:53,740 --> 00:06:57,130 So that is what a lower bound is, same thing, just kind of flipped. 91 00:06:57,670 --> 00:06:58,210 So. 92 00:06:59,210 --> 00:07:06,530 Yeah, if you're comparing it to the upper bound there, so you might think that, yeah, this doesn't 93 00:07:06,530 --> 00:07:13,190 seem like a great definition, how would we really define the runtime complexity of the read function 94 00:07:13,190 --> 00:07:14,090 in question? 95 00:07:15,010 --> 00:07:18,230 You know, how do we how do we really define it by bounding it like this? 96 00:07:18,230 --> 00:07:19,940 So they're a little bit loose? 97 00:07:20,180 --> 00:07:25,700 If we want something more tighter and more accurate, we can use something called theta, which is upper 98 00:07:25,700 --> 00:07:29,480 and lower bounds kind of squeezing our line there. 99 00:07:29,510 --> 00:07:35,750 So here we have both upper and lower bounds for the red line, and they are much tighter bounds. 100 00:07:36,290 --> 00:07:45,080 And both the upper and lower bounding functions, we can say that we have a theta and exact bound because 101 00:07:45,080 --> 00:07:48,560 they are the same magnitude as the Red Line function. 102 00:07:49,370 --> 00:07:57,560 So you notice that our red line function is in our blue, our upper blue line is two in and our lower 103 00:07:57,560 --> 00:07:59,210 blue line is zero point five in. 104 00:07:59,450 --> 00:08:05,060 They should remember back to when we first did Bigo and talked about basic operations and time complexity. 105 00:08:05,360 --> 00:08:11,330 We can throw away these constants when we have our final answer for these bounds. 106 00:08:11,780 --> 00:08:18,020 And so when you get rid of the contents, the constants you notice that they all have the same magnitude, 107 00:08:18,020 --> 00:08:20,150 they are all really in. 108 00:08:20,960 --> 00:08:30,560 So because of that, we can say that theta in is an exact abound on our function. 109 00:08:30,560 --> 00:08:36,470 And so that's like an upper and lower sandwich unit, and we are able to use Theta because it has the 110 00:08:36,470 --> 00:08:37,200 same magnitude. 111 00:08:37,200 --> 00:08:38,550 It's a more exact bound. 112 00:08:39,200 --> 00:08:45,440 We are able to say theta of and is a tight bound on this function. 113 00:08:45,440 --> 00:08:50,330 So tip balance are sometimes pretty difficult to compute. 114 00:08:50,600 --> 00:08:57,980 So that's part of why the industry often uses upper bounds because it's a little easier to compute. 115 00:08:57,980 --> 00:09:01,760 Sometimes side balance are almost impossible to compute for certain situations. 116 00:09:03,880 --> 00:09:11,620 So big, oh yeah, it's used a lot in industry, but it's nice to have an exact bound sometimes. 117 00:09:13,790 --> 00:09:19,340 So something that I want to point out is that best case, worst case, average case, all these cases, 118 00:09:19,340 --> 00:09:20,840 they are not the same thing as balance. 119 00:09:20,840 --> 00:09:24,080 So Big O is not worst case. 120 00:09:24,140 --> 00:09:26,800 Don't associate that with meaning. 121 00:09:26,810 --> 00:09:28,750 Worst case, that is not what it means. 122 00:09:28,760 --> 00:09:30,620 We talked about it in an upper bound. 123 00:09:30,800 --> 00:09:33,710 Of course, these things are used together quite often. 124 00:09:34,710 --> 00:09:39,000 But they don't literally mean big oh, doesn't literally mean best case. 125 00:09:39,150 --> 00:09:48,180 And that kids can that kind of gets mixed up a lot in a lot of academic setting and the industry setting 126 00:09:48,180 --> 00:09:48,750 as well. 127 00:09:48,750 --> 00:09:52,950 Just a lot of people think that it's that it's the same thing, but it's not. 128 00:09:53,640 --> 00:09:55,080 So just wanted to point that out. 129 00:09:55,650 --> 00:10:00,540 It is possible to consider an upper bound for best case analysis. 130 00:10:00,540 --> 00:10:06,330 So, you know, even though that doesn't necessarily make as much sense as looking in at an upper bound 131 00:10:06,330 --> 00:10:08,100 for worst case analysis, it is possible. 132 00:10:08,100 --> 00:10:12,720 And so I wanted to show that separation there, that they are not the exact same thing. 133 00:10:12,720 --> 00:10:17,940 We're talking about two different things that you kind of use both of them to solve for time complexity 134 00:10:17,940 --> 00:10:18,660 of an algorithm. 135 00:10:18,660 --> 00:10:27,410 But those symbols omega and theta and big O, they are not the state of definitions of cases. 136 00:10:27,420 --> 00:10:27,750 So. 137 00:10:28,860 --> 00:10:29,720 I want to point that out. 138 00:10:30,680 --> 00:10:34,880 So with that said, cases are something you consider before finding the balance, so you first need 139 00:10:34,880 --> 00:10:36,920 to decide what you're actually looking at. 140 00:10:36,950 --> 00:10:43,370 Am I looking at the worst case performance of this algorithm or the best case performance you choose 141 00:10:43,370 --> 00:10:50,520 what bounding type you think is appropriate to get the best possible analysis of the algorithm? 142 00:10:51,470 --> 00:10:55,310 And that's really what you're trying to do after you decide on the case. 143 00:10:56,840 --> 00:10:58,640 So let's look at some examples. 144 00:10:59,090 --> 00:11:05,000 Let's say we're going to do a really simple example here, but if we're doing a linear sequential search 145 00:11:05,510 --> 00:11:08,630 through an array looking for a specific element. 146 00:11:09,290 --> 00:11:13,640 So the best case, of course, would be if the element was the very first thing in the list. 147 00:11:13,640 --> 00:11:16,340 So right when we start out, we index the first thing. 148 00:11:16,730 --> 00:11:19,400 So array of zero first position. 149 00:11:19,550 --> 00:11:20,600 That's the best case. 150 00:11:20,600 --> 00:11:22,430 And that would just be Constantine, right? 151 00:11:22,430 --> 00:11:27,050 Because we're just performing a single index on the array and we found it and we're done. 152 00:11:28,570 --> 00:11:32,800 So it would be something or it could say like, you know, bingo of one. 153 00:11:33,800 --> 00:11:40,460 If we wanted to put an upper bound on that, the worst case, so that's either whether we look all the 154 00:11:40,460 --> 00:11:43,720 way to the very last element in the array. 155 00:11:43,730 --> 00:11:47,860 So let's say the very last element is the thing we're looking for or it's not in there at all. 156 00:11:47,870 --> 00:11:55,250 So either way, we had to look through the entire array of size and input in to either find it or not 157 00:11:55,250 --> 00:11:55,680 find it. 158 00:11:55,710 --> 00:11:57,200 We had to look through the whole array. 159 00:11:57,980 --> 00:11:59,690 So that would be the worst case. 160 00:12:00,940 --> 00:12:06,460 In an average case, we're just really looking at the average number of steps taken to find that element 161 00:12:06,460 --> 00:12:12,010 in the array when it really could be anywhere, it could be the fourth element, it could be the hundred 162 00:12:12,010 --> 00:12:14,320 thousandth element or something like that. 163 00:12:15,310 --> 00:12:19,000 So it's looking at that being averaged out. 164 00:12:21,130 --> 00:12:22,930 So one more thing. 165 00:12:23,560 --> 00:12:27,520 There is also a little low and little omega. 166 00:12:28,000 --> 00:12:35,740 So when we talked about big, oh, we were talking about it needing to be greater than or equal to the 167 00:12:35,740 --> 00:12:39,070 red line when we multiply it by some constant. 168 00:12:39,310 --> 00:12:46,810 And for Big Omega, it needed to be less than or equal to the Red Line when we were multiplying it by 169 00:12:46,810 --> 00:12:47,620 some constant. 170 00:12:48,680 --> 00:12:56,510 So little, Irwin, little Omega are just kind of looser descriptions, looser bounds on honor function, 171 00:12:56,510 --> 00:12:59,690 and those are not they they don't have the or equal. 172 00:12:59,690 --> 00:13:06,710 It's just littlo is just greater than and a little omega is just less than. 173 00:13:06,720 --> 00:13:07,930 So that's the only difference. 174 00:13:07,940 --> 00:13:12,350 You probably won't use this as much when you're doing analysis of algorithms, but I wanted to put it 175 00:13:12,350 --> 00:13:18,170 out there because it is kind of part of this subject, and I believe it needed to be mentioned. 176 00:13:20,220 --> 00:13:26,280 So that is all I have for the introduction to this new section in the next lectures, we will be looking 177 00:13:26,280 --> 00:13:29,910 at doing these more formal analyses on the algorithms. 178 00:13:30,030 --> 00:13:32,700 And so with that, I will see you in the next election, you.