1 00:00:00,860 --> 00:00:01,460 OK. 2 00:00:01,670 --> 00:00:09,350 Welcome to the second part of this course where we will be looking at data structures and algorithms, 3 00:00:09,770 --> 00:00:15,860 and we will be implementing these in C++, but there is also a theoretical component to this part of 4 00:00:15,860 --> 00:00:16,430 the course. 5 00:00:17,000 --> 00:00:23,540 And one of those theoretical components that we are going to start out with is going to be the efficiency 6 00:00:23,840 --> 00:00:26,750 of our algorithms and data structures. 7 00:00:27,890 --> 00:00:35,390 So of course, in this modern world, we care about how fast things run and how much space we can save. 8 00:00:35,720 --> 00:00:37,920 And so we're going to look into those two things. 9 00:00:37,940 --> 00:00:46,100 But first, we're going to look into time complexity, which is the runtime efficiency of a program 10 00:00:46,340 --> 00:00:49,430 also referred to as Big O an industry. 11 00:00:50,270 --> 00:00:51,770 So let's go ahead and get started. 12 00:00:54,130 --> 00:01:01,180 So we're going to just do a really basic overview of this, and the point is just to have a metric so 13 00:01:01,180 --> 00:01:07,990 we can properly evaluate the performance of our algorithms and data structures. 14 00:01:08,380 --> 00:01:10,860 And so are just going to gloss over some terms here. 15 00:01:10,870 --> 00:01:19,420 If you have some academic background in runtime efficiency and time complexity calculation and proving 16 00:01:19,420 --> 00:01:22,410 it and all of that, you might be thinking there's a lot more to this. 17 00:01:22,420 --> 00:01:23,620 It's not just bingo. 18 00:01:24,070 --> 00:01:29,350 There are terms like Big Omega and Theta and things like that. 19 00:01:29,650 --> 00:01:35,050 We all get into that later in the course where we look at more formal methods of evaluating this stuff 20 00:01:35,860 --> 00:01:37,600 with summations and recurrent formulas. 21 00:01:37,600 --> 00:01:43,300 But right now, we're just kind of going over it enough so we can start thinking about these things 22 00:01:43,300 --> 00:01:48,430 when we're writing code for our algorithms and coming up with strategies for our algorithms and data 23 00:01:48,430 --> 00:01:49,000 structures. 24 00:01:50,180 --> 00:01:51,650 OK, so let's get started. 25 00:01:52,370 --> 00:01:53,900 So what does it really mean? 26 00:01:54,120 --> 00:01:58,520 Well, it's how fast or slow a specific piece of code or algorithm is. 27 00:01:58,970 --> 00:02:05,540 And if you look at this chart down here, we can see that there's a few different graphs on here that 28 00:02:05,660 --> 00:02:08,630 have varying degrees of steepness and shape. 29 00:02:09,200 --> 00:02:14,690 So on the x axis, we have our elements and on the y axis we have operations. 30 00:02:15,140 --> 00:02:18,080 And what's happening is what we want to consider. 31 00:02:19,100 --> 00:02:24,170 Is the how are algorithm's performance changes? 32 00:02:25,160 --> 00:02:33,200 As we have an increased amount of input coming in, so we're going to refer to the input size as in. 33 00:02:33,530 --> 00:02:42,440 And then we care about as that increases here, how does the number of operations increase? 34 00:02:43,310 --> 00:02:45,560 So how much work is it having to do? 35 00:02:45,980 --> 00:02:53,480 So as we increase, that is the what is the rate of change, you know, if it becoming steeper, like 36 00:02:53,480 --> 00:02:54,980 how quickly does it become steeper? 37 00:02:54,980 --> 00:02:57,310 And we can see a different price difference between these lines. 38 00:02:57,320 --> 00:03:03,500 We have some linear ones down here that are in this green zone and we would consider those down here 39 00:03:04,130 --> 00:03:08,390 better time complexities than these ones up here in this red zone. 40 00:03:09,870 --> 00:03:16,590 And you can see Big O event, we know of one of log in and log in, we're going to get into the specifics 41 00:03:16,590 --> 00:03:17,610 of those later on. 42 00:03:17,880 --> 00:03:22,140 We're going to go over some simple examples today just so you get the overall idea of it. 43 00:03:24,370 --> 00:03:30,130 So for a first example, we're going to go ahead and look over at this piece of code over here, so 44 00:03:30,130 --> 00:03:31,720 it's just a simple for loop. 45 00:03:32,680 --> 00:03:39,070 And we have it starting in zero and going up until one less than in, so be in minus one. 46 00:03:39,340 --> 00:03:45,010 So since we're starting zero and it will run on the 0th time, we know that there is going to this is 47 00:03:45,010 --> 00:03:46,600 going to run for in times. 48 00:03:47,290 --> 00:03:52,720 What we want to do is choose a basic operation and here we have three to choose from. 49 00:03:53,150 --> 00:03:56,130 You're probably wondering, OK, how what one should I choose? 50 00:03:56,140 --> 00:03:56,950 How do I know? 51 00:03:57,220 --> 00:04:01,540 Of course, operations are different, but right now we're going to ignore that and we're just going 52 00:04:01,540 --> 00:04:04,030 to pick one and I'm going to go ahead and pick multiplication. 53 00:04:05,500 --> 00:04:12,040 So since this rise in times, we can see that this multiplication here is going to happen in times as 54 00:04:12,040 --> 00:04:12,520 well. 55 00:04:13,240 --> 00:04:21,070 And in fact, yeah, for every time this runs, we will also run this operation once every time, every 56 00:04:21,070 --> 00:04:22,090 iteration of the loop. 57 00:04:23,020 --> 00:04:28,780 So if we look over here two graphs, that is the explanation for why it is this and linear graph. 58 00:04:28,780 --> 00:04:30,430 And I know this is kind of a shabby graph. 59 00:04:30,440 --> 00:04:31,450 Just bear with me. 60 00:04:31,690 --> 00:04:35,530 I just kind of threw together some graphs just enough to explain the point of these things. 61 00:04:36,130 --> 00:04:42,790 But this line is our big go of in, and we say that because it happens in times and as we can see. 62 00:04:44,880 --> 00:04:52,230 As our input is increasing at a certain rate, it is the same for our number of operations. 63 00:04:52,560 --> 00:04:57,210 And that leads that is what leads us to call this linear time. 64 00:04:58,940 --> 00:05:04,790 OK, so one simple example out of the way, let's move on to the next one. 65 00:05:06,620 --> 00:05:13,640 So, Constantine, for this, we're looking at this code right here, and we noticed that there isn't 66 00:05:13,640 --> 00:05:15,140 even really a for loop here. 67 00:05:16,510 --> 00:05:18,760 And so we'll say, OK, let's do what we did before. 68 00:05:19,060 --> 00:05:20,800 Let's choose a basic operation. 69 00:05:21,040 --> 00:05:23,440 Let's go ahead and look at Edition. 70 00:05:23,800 --> 00:05:25,930 When you say, well, there's three additions. 71 00:05:26,840 --> 00:05:30,040 Hmm, I guess I'll just say bingo of three. 72 00:05:30,640 --> 00:05:33,190 And that is a correct way of thinking. 73 00:05:33,910 --> 00:05:40,780 But what we do for something we consider cost and time is we just simplify it to one. 74 00:05:41,440 --> 00:05:48,460 And that is whenever we have some constant in here that we see, no matter how big it is, we're just 75 00:05:48,460 --> 00:05:49,870 going to bring it down to one. 76 00:05:50,200 --> 00:05:56,050 And the reason is is because if we look at this line over here and we think about what it means to have 77 00:05:56,050 --> 00:06:04,450 some cost and time operation as our input changes increases what I should say, we don't really see 78 00:06:04,600 --> 00:06:10,360 a change in how it affects this piece of code here. 79 00:06:11,500 --> 00:06:17,560 Basically, you could put as many of these editions as you wanted, and all we would really do is raise 80 00:06:17,560 --> 00:06:19,720 this horizontal line up. 81 00:06:20,590 --> 00:06:23,620 But the fact is is it would still be a horizontal line. 82 00:06:23,920 --> 00:06:29,890 And what we care about is the line itself and how steep it gets. 83 00:06:30,490 --> 00:06:33,550 We're looking for that change, you know, as we add the input. 84 00:06:34,410 --> 00:06:41,280 And something that's really important in comparing cost and time to the linear time we saw before is 85 00:06:41,280 --> 00:06:49,230 thinking that if we go back here and we take this line and we put it on this graph, even if I was to 86 00:06:49,230 --> 00:06:55,890 bring this oh of one line way up, let's say that we had one plus two plus three plus four all the way 87 00:06:55,890 --> 00:07:03,840 up to five hundred and I brought this line way up or even a million at some point that oh of in line 88 00:07:04,140 --> 00:07:07,980 is going to cross this of one line. 89 00:07:08,850 --> 00:07:16,500 And that is important because that is what we can look at to help us understand why would Constantine 90 00:07:16,890 --> 00:07:19,020 be better than linear time? 91 00:07:19,620 --> 00:07:26,820 If I go back here, we see there is an oh of one and it's way down here and that is better than our 92 00:07:26,970 --> 00:07:29,160 linear time, which is in the yellow zone here. 93 00:07:29,820 --> 00:07:31,980 And that is the reason I want to point out. 94 00:07:32,010 --> 00:07:36,570 It's because at some point that oh of in line would cross this cost and time line. 95 00:07:39,240 --> 00:07:40,980 So let's look at another example. 96 00:07:41,520 --> 00:07:43,500 This is another linear example. 97 00:07:43,800 --> 00:07:44,580 But why? 98 00:07:44,910 --> 00:07:46,800 Let's take a deeper look into it. 99 00:07:46,800 --> 00:07:53,740 So we have another for loop and this for loop is going for the same amount of times that previous for 100 00:07:53,740 --> 00:07:54,690 a loop that we looked at. 101 00:07:55,020 --> 00:07:59,190 It's there starts to zero, goes up to one less than in. 102 00:07:59,490 --> 00:08:03,030 And we just have this one statement in here that we want to execute. 103 00:08:04,110 --> 00:08:07,500 We have a similar for loop down here, but it just goes backwards. 104 00:08:07,500 --> 00:08:10,680 It's decreasing and it starts to end and goes down to zero. 105 00:08:12,480 --> 00:08:19,830 So if we looked at this intuitively, we might say, OK, well in times here and in times here, and 106 00:08:19,830 --> 00:08:21,240 we do in plus in. 107 00:08:23,220 --> 00:08:30,330 So in-person would be two in, and that is correct in thinking that, but what we're going to do is 108 00:08:30,330 --> 00:08:35,100 actually generalize that more interrupt this constant and just call it O event. 109 00:08:35,730 --> 00:08:39,510 And you see, as we go on, this is kind of the way we do things. 110 00:08:39,510 --> 00:08:44,850 We think, Oh, we're really only interested actually in the largest term. 111 00:08:45,300 --> 00:08:52,440 So if we were to have like more things in here, Constance, and you know, you have some kind of polynomial. 112 00:08:52,740 --> 00:08:53,210 No, I wouldn't. 113 00:08:53,850 --> 00:08:58,530 I would just say, actually, you have some kind of expression in here and then we would just have like 114 00:08:58,530 --> 00:09:00,750 two men plus two or something like that. 115 00:09:00,960 --> 00:09:02,460 It would still just be in. 116 00:09:03,530 --> 00:09:08,570 So that's why we're getting rid of that constant, and you'll notice that we continue to do that even 117 00:09:08,570 --> 00:09:10,190 with more complex examples. 118 00:09:12,810 --> 00:09:19,140 So let's look at a more complex example, and for this one, we see this code over here, but what I 119 00:09:19,140 --> 00:09:26,400 want you to do is instead of this being I less than equal to N and J less than or equal to N. 120 00:09:26,820 --> 00:09:35,520 Let's just pretend that it was just I less than in N.J., less than a in here is there's not a lot going 121 00:09:35,520 --> 00:09:37,440 on in here besides this count plus plus. 122 00:09:37,650 --> 00:09:39,930 So let's use that as our basic operation. 123 00:09:40,440 --> 00:09:47,430 So go ahead and pause this video and see if you can work it out in your head or on paper what you think 124 00:09:47,850 --> 00:09:50,460 the time complexity would be. 125 00:09:50,820 --> 00:09:57,510 And if you believe that it is o n squared, think about why would it be n squared? 126 00:09:59,030 --> 00:10:03,080 So, mind you, we're not talking about this equals sign right now. 127 00:10:03,110 --> 00:10:06,980 Just pretend it's I less than an and j less than in. 128 00:10:08,970 --> 00:10:17,370 OK, so if you went ahead and looked at that, you might have thought, OK, well, I'm going to first 129 00:10:17,370 --> 00:10:23,010 look at this interview and see that this happens in times. 130 00:10:23,010 --> 00:10:29,220 And of course, that's we're still talking about this G8 less than in and I listen in now with the equal 131 00:10:29,220 --> 00:10:29,910 sign right now. 132 00:10:30,870 --> 00:10:40,140 So if I go in times here and then that whole thing is happening in times here so I can go in times in 133 00:10:40,770 --> 00:10:42,960 and in times in is in squared. 134 00:10:43,930 --> 00:10:47,440 That would be the correct way of thinking, and that is in fact correct. 135 00:10:47,860 --> 00:10:56,380 If you just have I listen in and listen in here, it would be a time complexity of o of n squared. 136 00:10:57,390 --> 00:11:04,680 And if we think back to some math that some of you might have done before or not, that would result 137 00:11:04,680 --> 00:11:06,660 in kind of a curved line here. 138 00:11:06,660 --> 00:11:12,660 If you think back to Paulette Parabolas and such, we're just looking at these Cartesian planes here. 139 00:11:13,320 --> 00:11:18,930 We're going to have a curve graph like this, and I know it's kind of a bad, poorly drawn graph, but 140 00:11:19,260 --> 00:11:20,940 you can get the picture of it. 141 00:11:22,040 --> 00:11:24,590 OK, so now let's look at this one. 142 00:11:25,550 --> 00:11:32,090 So if we have less than or equal to N is pretty much the same thing. 143 00:11:32,780 --> 00:11:38,930 But what we're doing is it's just it's just like only slightly more complicated as far as these terms 144 00:11:38,930 --> 00:11:39,080 here. 145 00:11:39,080 --> 00:11:41,000 But essentially we're doing the same thing. 146 00:11:42,410 --> 00:11:46,600 This happens in plus one times because we're doing less than or equal to. 147 00:11:46,610 --> 00:11:47,650 It's one more now. 148 00:11:49,030 --> 00:11:50,800 And same with this outer loop. 149 00:11:51,220 --> 00:11:56,320 So in +1 times, in +1, we get n squared plus two in plus one. 150 00:11:57,070 --> 00:12:01,300 Like I was mentioning before, we're going to drop the constants, so we're going to drop this added 151 00:12:01,300 --> 00:12:04,740 cost around here and we're going to drop this constant here. 152 00:12:04,750 --> 00:12:10,840 Similar to when we were back here, we had this two in and we got rid of the two. 153 00:12:12,410 --> 00:12:17,840 We're going to go ahead and do that for both of these, and then we have O and Squared Plus in. 154 00:12:18,380 --> 00:12:22,730 But actually, like I mentioned before, we're really only interested in the largest term. 155 00:12:22,730 --> 00:12:27,110 So we're even going to get rid of this in because this is bigger. 156 00:12:27,560 --> 00:12:35,540 This is basically a worse if you were to just have of in and o n squared and compare them side by side. 157 00:12:37,130 --> 00:12:38,810 You could draw this on your graph here. 158 00:12:39,050 --> 00:12:46,340 You would notice that in squared ons, Owen is a worse time complexity than in it because it grows at 159 00:12:46,340 --> 00:12:47,360 a faster rate. 160 00:12:47,750 --> 00:12:52,850 So that is why we're going to drop the N because we really only care about the term that's like the 161 00:12:52,850 --> 00:12:54,710 largest, the largest magnitude. 162 00:12:56,290 --> 00:13:01,690 OK, so hopefully this has explained enough for you to get by with the basics of Big O. 163 00:13:01,720 --> 00:13:08,080 Like I said later, we're going to go into more formal analyses of these things using summations and 164 00:13:08,980 --> 00:13:12,120 recurrence formulas, a little bit of math that we might have to brush up on. 165 00:13:13,390 --> 00:13:17,590 But right now, this is enough for us to get by in the first part of this series. 166 00:13:18,010 --> 00:13:22,270 I definitely encourage you to go online and look up more about time complexity. 167 00:13:22,270 --> 00:13:28,090 If there's any gaps that are here and I will try and provide some links that can help you do that. 168 00:13:28,540 --> 00:13:30,230 All right, I'll see you in the next lecture.