1 00:00:00,180 --> 00:00:02,310 -: So there's another component of measuring algorithms, 2 00:00:02,310 --> 00:00:04,200 which is space complexity. 3 00:00:04,200 --> 00:00:07,060 So what is, what are the space complexities 4 00:00:08,520 --> 00:00:10,653 of both of these algorithms? 5 00:00:11,790 --> 00:00:14,280 So let's see if it can tell us that too, right? 6 00:00:14,280 --> 00:00:16,140 So does it really understand what's going on? 7 00:00:16,140 --> 00:00:20,520 Does it like actually comprehend? Not so much, but it does. 8 00:00:20,520 --> 00:00:23,040 It is able to generate likely sequences of words that kind 9 00:00:23,040 --> 00:00:25,440 of make sense in the given context. 10 00:00:25,440 --> 00:00:30,440 So space complexity of deceive is O{x}. 11 00:00:30,720 --> 00:00:32,640 The reason for that is we actually go ahead 12 00:00:32,640 --> 00:00:34,593 and create an entire array, 13 00:00:35,760 --> 00:00:37,410 one for each of the numbers, right? 14 00:00:37,410 --> 00:00:40,800 So that's why that is O{x}. 15 00:00:40,800 --> 00:00:43,350 Yes, So we create a Boolean array 16 00:00:43,350 --> 00:00:46,620 and the space complexity of the trial division is O{1} 17 00:00:46,620 --> 00:00:49,380 because we're not actually storing, 18 00:00:49,380 --> 00:00:50,640 we're not actually creating any 19 00:00:50,640 --> 00:00:53,130 auxiliary structures to help us, right? 20 00:00:53,130 --> 00:00:55,860 We're just the only create space that we're creating is 21 00:00:55,860 --> 00:00:57,750 to store the output itself. 22 00:00:57,750 --> 00:01:01,620 So that's kind of the trade-off that we've got going here. 23 00:01:01,620 --> 00:01:04,620 The Sieve does have some space involved, 24 00:01:04,620 --> 00:01:06,450 but it runs much faster. 25 00:01:06,450 --> 00:01:09,720 Whereas the trail division one has 26 00:01:09,720 --> 00:01:12,580 no extra space, though it does have 27 00:01:13,860 --> 00:01:16,990 a much much worse runtime as we get to hire 28 00:01:18,060 --> 00:01:20,970 bigger sized outputs or inputs. 29 00:01:20,970 --> 00:01:23,610 So yeah, this is pretty interesting that it's able 30 00:01:23,610 --> 00:01:24,900 to come up with all this for us 31 00:01:24,900 --> 00:01:27,960 and even sort of tell us how they perform 32 00:01:27,960 --> 00:01:30,153 in terms of space and time. 33 00:01:31,080 --> 00:01:33,510 So if we actually go over 34 00:01:33,510 --> 00:01:36,570 to this very popular website called Leet Code, 35 00:01:36,570 --> 00:01:38,100 we can actually try to see 36 00:01:38,100 --> 00:01:40,680 if Chat GPT can solve one of these questions. 37 00:01:40,680 --> 00:01:43,380 So let's actually bring this over 38 00:01:43,380 --> 00:01:46,020 to over here 39 00:01:46,020 --> 00:01:48,750 and we can see, let me zoom in on this for you. 40 00:01:48,750 --> 00:01:50,550 So this happens to be the daily question of the day. 41 00:01:50,550 --> 00:01:54,240 So Leet Code is a very popular website that's used for 42 00:01:54,240 --> 00:01:56,700 software engineers preparing for their interviews. 43 00:01:56,700 --> 00:02:00,840 And basically they're gonna ask you this sort of, 44 00:02:00,840 --> 00:02:01,980 not really brain teaser, 45 00:02:01,980 --> 00:02:04,410 but like sometimes they're brain teasers, 46 00:02:04,410 --> 00:02:07,380 but they're basically just questions that basically ask you 47 00:02:07,380 --> 00:02:10,620 to implement a solution to in code of your, 48 00:02:10,620 --> 00:02:12,900 or in the language of your choice, right? 49 00:02:12,900 --> 00:02:15,270 So this question right here 50 00:02:15,270 --> 00:02:17,850 is called single element in assorted array. 51 00:02:17,850 --> 00:02:18,990 You're given a sorted array. 52 00:02:18,990 --> 00:02:21,150 So basically a sequence of elements 53 00:02:21,150 --> 00:02:22,710 and it's consisting only of integers. 54 00:02:22,710 --> 00:02:26,340 So whole numbers and every element appears exactly twice 55 00:02:26,340 --> 00:02:29,400 except for one element which appears exactly once. 56 00:02:29,400 --> 00:02:31,200 And we're gonna want to return this single element 57 00:02:31,200 --> 00:02:32,790 that appears only once 58 00:02:32,790 --> 00:02:34,440 and our solution must run in 59 00:02:34,440 --> 00:02:36,450 O{log n} time and O{1} space. 60 00:02:36,450 --> 00:02:38,790 So this off the top of my head, 61 00:02:38,790 --> 00:02:41,010 sounds like a binary search problem 62 00:02:41,010 --> 00:02:42,600 due to the fact that it's sorted. 63 00:02:42,600 --> 00:02:45,000 So if you're familiar with that at all, 64 00:02:45,000 --> 00:02:47,190 that would explain the log{n} runtime. 65 00:02:47,190 --> 00:02:50,370 So basically it's gonna be looking like halfway through 66 00:02:50,370 --> 00:02:51,990 checking if it's less than a right 67 00:02:51,990 --> 00:02:54,780 and kind of probing for that, right? 68 00:02:54,780 --> 00:02:56,580 So if we go ahead 69 00:02:56,580 --> 00:03:00,694 and maybe let's actually see if it can read. 70 00:03:00,694 --> 00:03:04,140 Could you solve the problem 71 00:03:04,140 --> 00:03:06,213 prescribed in the following link? 72 00:03:08,070 --> 00:03:10,500 Here's a solution to the problem. Single element. 73 00:03:10,500 --> 00:03:12,000 It sorted away from Leet Code. 74 00:03:12,000 --> 00:03:14,640 So it's right now it actually went into that link 75 00:03:14,640 --> 00:03:17,580 that I sent it and it's reading out the problem 76 00:03:17,580 --> 00:03:20,280 and the examples and hopefully it's gonna 77 00:03:20,280 --> 00:03:21,720 give us a correct solution. 78 00:03:21,720 --> 00:03:23,910 And the reason why this is gonna be pretty cool is 79 00:03:23,910 --> 00:03:27,000 because Leet Code actually has a grader. 80 00:03:27,000 --> 00:03:31,230 So we're gonna be able to test our solution against 81 00:03:31,230 --> 00:03:34,470 a suite of tests that will verify its robustness 82 00:03:34,470 --> 00:03:38,790 as a solution and see if it also meets this 83 00:03:38,790 --> 00:03:40,920 runtime requirement, which is 84 00:03:40,920 --> 00:03:42,720 that it must run an O{log n} time. 85 00:03:42,720 --> 00:03:45,570 So in computer science you can write all types of code 86 00:03:45,570 --> 00:03:47,925 to solve the same problem, but as we saw before 87 00:03:47,925 --> 00:03:50,250 in the case of generating all the primes up 88 00:03:50,250 --> 00:03:52,140 to a certain number, it's often the case 89 00:03:52,140 --> 00:03:55,140 where one algorithm might be better than another 90 00:03:55,140 --> 00:03:57,813 in terms of the space time trade off. 91 00:03:58,800 --> 00:04:01,500 So if we go ahead and look over here 92 00:04:01,500 --> 00:04:03,450 once again, the code snippet has been annotated 93 00:04:03,450 --> 00:04:04,530 by the incorrect language. 94 00:04:04,530 --> 00:04:09,000 Well, this is not a SQL script by any stretch, 95 00:04:09,000 --> 00:04:10,590 not even sync tactically. 96 00:04:10,590 --> 00:04:12,330 But if we go ahead and copy that code, 97 00:04:12,330 --> 00:04:14,613 we can actually bring that into here. 98 00:04:15,480 --> 00:04:16,440 One thing I will note though is 99 00:04:16,440 --> 00:04:18,720 that it actually deleted the class declaration 100 00:04:18,720 --> 00:04:20,490 for solution, which we actually do need. 101 00:04:20,490 --> 00:04:22,890 And it also got rid of something here, which we do need. 102 00:04:22,890 --> 00:04:25,950 So if we go ahead and patch that up real quick 103 00:04:25,950 --> 00:04:28,860 and we run that, let's see if it actually runs, 104 00:04:28,860 --> 00:04:33,860 passes the test cases and Python is indentation sensitive, 105 00:04:33,862 --> 00:04:36,570 so let's go ahead and indent that as well. 106 00:04:36,570 --> 00:04:40,290 And sure enough it accepts, which is pretty awesome. 107 00:04:40,290 --> 00:04:42,870 Now, one thing I will warn against is that 108 00:04:42,870 --> 00:04:45,270 there's probably some solutions in here 109 00:04:45,270 --> 00:04:48,660 that it could have very easily just pulled straight from. 110 00:04:48,660 --> 00:04:51,720 However, this is locked behind a paywall, I believe. 111 00:04:51,720 --> 00:04:53,910 So yeah, it definitely didn't look there. 112 00:04:53,910 --> 00:04:56,070 So we can see that it's accepted. 113 00:04:56,070 --> 00:04:59,190 This is only on two very small test cases though, 114 00:04:59,190 --> 00:05:00,960 so let's go ahead and submit that. 115 00:05:00,960 --> 00:05:03,450 That's gonna run against many many more tests. 116 00:05:03,450 --> 00:05:04,770 So if it actually passes this, 117 00:05:04,770 --> 00:05:06,420 we'll know it's actually good to go. 118 00:05:06,420 --> 00:05:09,210 And that's so cool, right? It actually works. 119 00:05:09,210 --> 00:05:11,040 So yeah, and it even gives us an explanation 120 00:05:11,040 --> 00:05:13,200 for what's going on here. 121 00:05:13,200 --> 00:05:14,490 It gives us the time complexity. 122 00:05:14,490 --> 00:05:16,260 It gives us the space complexity. 123 00:05:16,260 --> 00:05:19,020 I almost kind of wonder if the reason it did that is 124 00:05:19,020 --> 00:05:21,750 because I asked about that for earlier question, 125 00:05:21,750 --> 00:05:23,670 which would be really cool. 126 00:05:23,670 --> 00:05:25,890 So yeah, we could see that actually just works. 127 00:05:25,890 --> 00:05:29,190 But what if we wanted it to be in Java? 128 00:05:29,190 --> 00:05:33,100 Could you give me Java code instead? 129 00:05:34,740 --> 00:05:38,820 Right? So that's one thing that could be super cool 130 00:05:38,820 --> 00:05:41,520 for sort of applications of Chat GPT 131 00:05:41,520 --> 00:05:43,890 as you could have written code in one language 132 00:05:43,890 --> 00:05:47,010 and maybe you want it to be in another language 133 00:05:47,010 --> 00:05:48,690 because of affordability reasons 134 00:05:48,690 --> 00:05:51,090 or whatever reason that you may want. 135 00:05:51,090 --> 00:05:52,860 And if you ask Chat GPT to like 136 00:05:52,860 --> 00:05:54,360 kind of generate the same code for 137 00:05:54,360 --> 00:05:57,270 that problem spec in a different language. 138 00:05:57,270 --> 00:05:58,470 It's probably able to do that 139 00:05:58,470 --> 00:06:00,450 And let's actually verify if it did it correctly. 140 00:06:00,450 --> 00:06:02,760 Once again, it incorrectly annotated the type 141 00:06:02,760 --> 00:06:04,680 or the code block here. 142 00:06:04,680 --> 00:06:08,130 But as long as you are familiar with coding languages, 143 00:06:08,130 --> 00:06:10,650 in fact let's actually run an experiment on that. 144 00:06:10,650 --> 00:06:12,750 I mean it's referencing this as Java code, 145 00:06:12,750 --> 00:06:15,060 but in case you really didn't know, 146 00:06:15,060 --> 00:06:16,800 you could probably try copying this code 147 00:06:16,800 --> 00:06:19,560 and then asking it what language is this written in? 148 00:06:19,560 --> 00:06:21,000 And it should probably say Java. 149 00:06:21,000 --> 00:06:22,680 cause I mean that's what it looks like, right? 150 00:06:22,680 --> 00:06:25,440 But without further delay, let's just copy that 151 00:06:25,440 --> 00:06:29,760 straight into Java, the Java code pen here, 152 00:06:29,760 --> 00:06:33,780 and let's submit that, see if it works. 153 00:06:33,780 --> 00:06:37,410 Sure enough, it is a correct solution once again. 154 00:06:37,410 --> 00:06:38,460 So that's really cool, right? 155 00:06:38,460 --> 00:06:41,460 Like you can translate between the two languages here, 156 00:06:41,460 --> 00:06:43,560 more or less using the same algorithm here. 157 00:06:43,560 --> 00:06:45,540 But yeah, that just really shows the power 158 00:06:45,540 --> 00:06:47,910 of Chat GPT in algorithms 159 00:06:47,910 --> 00:06:49,140 and look forward to seeing you 160 00:06:49,140 --> 00:06:51,993 in the next video about debugging.