1 00:00:00,420 --> 00:00:03,510 ‫So now let's wrap up Big O. 2 00:00:04,610 --> 00:00:08,030 ‫So I'm going to bring up our graph here and say it is 100. 3 00:00:08,270 --> 00:00:11,720 ‫Let's look at what each of these four are. 4 00:00:12,080 --> 00:00:13,740 ‫When in is 100. 5 00:00:13,760 --> 00:00:18,740 ‫So we start on the bottom there with over one and that's going to equal one. 6 00:00:19,870 --> 00:00:23,410 ‫O of log in is going to be approximately seven. 7 00:00:24,400 --> 00:00:27,160 ‫O of n is going to be a hundred because. 8 00:00:27,160 --> 00:00:28,120 ‫And is 100. 9 00:00:29,110 --> 00:00:32,370 ‫And then squared is 10,000. 10 00:00:32,380 --> 00:00:39,520 ‫So you can already see that there's a very big difference between each of these and that o of n squared 11 00:00:39,850 --> 00:00:47,560 ‫compared to the other three is very inefficient, but this spread becomes even bigger. 12 00:00:48,150 --> 00:00:50,630 ‫When in becomes larger. 13 00:00:50,640 --> 00:00:54,570 ‫So let's look at what happens when in is 1000. 14 00:00:55,530 --> 00:01:04,350 ‫O of one down on the bottom there is going to still be one it's not affected by in becoming larger oh 15 00:01:04,350 --> 00:01:10,740 ‫of login is approximately ten because two to the 10th power is 1024. 16 00:01:10,740 --> 00:01:12,750 ‫So 1000 is pretty close to that. 17 00:01:12,750 --> 00:01:14,700 ‫So we'll call that approximately ten. 18 00:01:14,970 --> 00:01:22,980 ‫But notice it only went from 7 to 10 even though in went from 100 to 1000. 19 00:01:24,250 --> 00:01:30,160 ‫Oh, Yvonne is going to be 1011 squared goes all the way to a million. 20 00:01:30,160 --> 00:01:35,440 ‫So as in gross in squared is going to grow very, very fast. 21 00:01:35,440 --> 00:01:40,000 ‫It's very inefficient compared to any of these others. 22 00:01:40,240 --> 00:01:46,330 ‫So we'll see as we get into the course, there will be situations where you do something and it's O 23 00:01:46,330 --> 00:01:50,500 ‫of n squared and you can rewrite the code and make it o of n. 24 00:01:50,740 --> 00:01:54,490 ‫That is a huge increase in efficiency when you can do that. 25 00:01:54,940 --> 00:01:58,330 ‫So now let's look at some terminology for all of these. 26 00:01:58,510 --> 00:02:02,200 ‫O of n squared is a loop within a loop. 27 00:02:03,400 --> 00:02:05,130 ‫All of MN is proportional. 28 00:02:05,140 --> 00:02:10,540 ‫It will always be a straight line of log in, divide and conquer. 29 00:02:10,540 --> 00:02:17,350 ‫When you hear that that is o of log in and o of one is constant time. 30 00:02:19,070 --> 00:02:25,430 ‫So those are our four terms for our four big O's that will see for most of the course. 31 00:02:25,880 --> 00:02:28,370 ‫So now I want to flip over to a website. 32 00:02:28,370 --> 00:02:32,210 ‫This is called Big O Cheat Sheet Dotcom. 33 00:02:32,690 --> 00:02:36,230 ‫At the very top of the page, you have this chart. 34 00:02:36,590 --> 00:02:40,290 ‫These two over here, we're not going to see in this course. 35 00:02:40,310 --> 00:02:44,150 ‫In fact, o of in factorial the one all the way to the left. 36 00:02:44,150 --> 00:02:51,890 ‫There is something that you would have to intentionally write bad code to achieve. 37 00:02:52,530 --> 00:02:59,100 ‫The worst one that we're going to see in this course is going to be o of n squared, which is in the 38 00:02:59,100 --> 00:03:00,240 ‫horrible category. 39 00:03:01,530 --> 00:03:03,540 ‫And we'll make our way across here. 40 00:03:04,110 --> 00:03:04,920 ‫Oh, of end times. 41 00:03:04,920 --> 00:03:05,410 ‫Log in. 42 00:03:05,430 --> 00:03:09,450 ‫Remember, we're going to see this in a couple of sorting algorithms. 43 00:03:09,870 --> 00:03:17,850 ‫And then down here is where we want to stay with these three o of n o of log in and o of one. 44 00:03:19,000 --> 00:03:21,550 ‫So below the chart if you scroll. 45 00:03:23,590 --> 00:03:27,400 ‫They have common data structure operations. 46 00:03:27,820 --> 00:03:30,670 ‫So you have a variety of data structures on the left there. 47 00:03:31,560 --> 00:03:36,450 ‫And this whole area is time complexity and is broken into. 48 00:03:36,480 --> 00:03:38,150 ‫Average on this side. 49 00:03:38,160 --> 00:03:42,180 ‫Notice these all start with the Greek letter theta. 50 00:03:42,910 --> 00:03:46,900 ‫And then worst on this side, this is going to be. 51 00:03:46,900 --> 00:03:51,910 ‫Oh, but also over here we have space complexity. 52 00:03:52,670 --> 00:03:57,620 ‫And this just has big O for space complexity, not omega or theta. 53 00:03:57,830 --> 00:04:04,190 ‫And you can see that except for one, the skipped list, which we're not going to build in this course, 54 00:04:04,340 --> 00:04:05,810 ‫they're all o of n. 55 00:04:06,410 --> 00:04:13,220 ‫And this is one of the reasons we're going to spend much more time on time complexity than space complexity, 56 00:04:13,370 --> 00:04:19,730 ‫because in the entire data structure section, all the space complexity is going to be the same. 57 00:04:20,440 --> 00:04:22,540 ‫So then if we scroll again. 58 00:04:23,590 --> 00:04:27,400 ‫You have array sorting algorithms. 59 00:04:28,280 --> 00:04:38,600 ‫And this has best with omega average theta worst zero for time complexity. 60 00:04:38,870 --> 00:04:43,610 ‫And then the space complexities are all over the place. 61 00:04:43,610 --> 00:04:46,700 ‫And this is where we will talk about space complexity. 62 00:04:47,400 --> 00:04:53,220 ‫And one of the things that's interesting is quicksort and merge sort up here at the top for the most 63 00:04:53,220 --> 00:04:55,860 ‫part is o of n times log in. 64 00:04:56,310 --> 00:05:00,750 ‫But the space complexity is not the best. 65 00:05:01,730 --> 00:05:08,150 ‫Whereas you get down here, we're going to build these three bubble sort, insertion sort and selection 66 00:05:08,150 --> 00:05:08,510 ‫sort. 67 00:05:08,510 --> 00:05:11,930 ‫And you can see the time complexities for the most part are not good. 68 00:05:11,930 --> 00:05:18,830 ‫They're olivine squared, but all three of them have a space complexity of o of one. 69 00:05:19,630 --> 00:05:26,770 ‫So these three are considered to be, shall we say, primitive sorting algorithms. 70 00:05:26,890 --> 00:05:33,970 ‫But from a space complexity, they're great also in a best possible scenario over here. 71 00:05:34,450 --> 00:05:39,760 ‫They are more efficient than quicksort or merge sort. 72 00:05:40,500 --> 00:05:47,340 ‫This situation, by the way, is if you have already sorted data or almost sorted data, then it's going 73 00:05:47,340 --> 00:05:48,660 ‫to be in. 74 00:05:48,840 --> 00:05:54,960 ‫And that's also the situation up here for quicksort when it has its worst possible scenario. 75 00:05:55,530 --> 00:06:01,020 ‫So let's say you have sorted data or almost sorted data, and that could happen if you have a sorted 76 00:06:01,020 --> 00:06:05,070 ‫list and you add one item to the end and then you're going to sort it. 77 00:06:05,100 --> 00:06:06,540 ‫It is almost sorted. 78 00:06:06,540 --> 00:06:12,090 ‫Or it could be that that item on the end is the highest number and it's completely sorted. 79 00:06:12,850 --> 00:06:15,730 ‫QuickSort is going to be terrible in a situation like that. 80 00:06:16,570 --> 00:06:20,270 ‫But bubble sort and insertion sort are going to be very good. 81 00:06:20,290 --> 00:06:25,150 ‫So these are the kinds of questions that you're going to get in an interview. 82 00:06:25,570 --> 00:06:31,570 ‫This is why you have to know the big oh and for that matter, the theta or the omega, in this case 83 00:06:32,170 --> 00:06:39,400 ‫for the time complexity and understand the space complexity to be able to answer these questions. 84 00:06:39,940 --> 00:06:45,820 ‫But also, I would encourage you to go to this website and spend some time looking this over. 85 00:06:46,090 --> 00:06:54,250 ‫After you start getting an idea of how this works in the course, I will add a link to this website 86 00:06:54,280 --> 00:06:56,710 ‫in the resources for this video. 87 00:06:57,850 --> 00:07:01,360 ‫And that is our wrap up for Big O.