-: So there's another component of measuring algorithms,
which is space complexity.
So what is, what are the space complexities
of both of these algorithms?
So let's see if it can tell us that too, right?
So does it really understand what's going on?
Does it like actually comprehend? Not so much, but it does.
It is able to generate likely sequences of words that kind
of make sense in the given context.
So space complexity of deceive is O{x}.
The reason for that is we actually go ahead
and create an entire array,
one for each of the numbers, right?
So that's why that is O{x}.
Yes, So we create a Boolean array
and the space complexity of the trial division is O{1}
because we're not actually storing,
we're not actually creating any
auxiliary structures to help us, right?
We're just the only create space that we're creating is
to store the output itself.
So that's kind of the trade-off that we've got going here.
The Sieve does have some space involved,
but it runs much faster.
Whereas the trail division one has
no extra space, though it does have
a much much worse runtime as we get to hire
bigger sized outputs or inputs.
So yeah, this is pretty interesting that it's able
to come up with all this for us
and even sort of tell us how they perform
in terms of space and time.
So if we actually go over
to this very popular website called Leet Code,
we can actually try to see
if Chat GPT can solve one of these questions.
So let's actually bring this over
to over here
and we can see, let me zoom in on this for you.
So this happens to be the daily question of the day.
So Leet Code is a very popular website that's used for
software engineers preparing for their interviews.
And basically they're gonna ask you this sort of,
not really brain teaser,
but like sometimes they're brain teasers,
but they're basically just questions that basically ask you
to implement a solution to in code of your,
or in the language of your choice, right?
So this question right here
is called single element in assorted array.
You're given a sorted array.
So basically a sequence of elements
and it's consisting only of integers.
So whole numbers and every element appears exactly twice
except for one element which appears exactly once.
And we're gonna want to return this single element
that appears only once
and our solution must run in
O{log n} time and O{1} space.
So this off the top of my head,
sounds like a binary search problem
due to the fact that it's sorted.
So if you're familiar with that at all,
that would explain the log{n} runtime.
So basically it's gonna be looking like halfway through
checking if it's less than a right
and kind of probing for that, right?
So if we go ahead
and maybe let's actually see if it can read.
Could you solve the problem
prescribed in the following link?
Here's a solution to the problem. Single element.
It sorted away from Leet Code.
So it's right now it actually went into that link
that I sent it and it's reading out the problem
and the examples and hopefully it's gonna
give us a correct solution.
And the reason why this is gonna be pretty cool is
because Leet Code actually has a grader.
So we're gonna be able to test our solution against
a suite of tests that will verify its robustness
as a solution and see if it also meets this
runtime requirement, which is
that it must run an O{log n} time.
So in computer science you can write all types of code
to solve the same problem, but as we saw before
in the case of generating all the primes up
to a certain number, it's often the case
where one algorithm might be better than another
in terms of the space time trade off.
So if we go ahead and look over here
once again, the code snippet has been annotated
by the incorrect language.
Well, this is not a SQL script by any stretch,
not even sync tactically.
But if we go ahead and copy that code,
we can actually bring that into here.
One thing I will note though is
that it actually deleted the class declaration
for solution, which we actually do need.
And it also got rid of something here, which we do need.
So if we go ahead and patch that up real quick
and we run that, let's see if it actually runs,
passes the test cases and Python is indentation sensitive,
so let's go ahead and indent that as well.
And sure enough it accepts, which is pretty awesome.
Now, one thing I will warn against is that
there's probably some solutions in here
that it could have very easily just pulled straight from.
However, this is locked behind a paywall, I believe.
So yeah, it definitely didn't look there.
So we can see that it's accepted.
This is only on two very small test cases though,
so let's go ahead and submit that.
That's gonna run against many many more tests.
So if it actually passes this,
we'll know it's actually good to go.
And that's so cool, right? It actually works.
So yeah, and it even gives us an explanation
for what's going on here.
It gives us the time complexity.
It gives us the space complexity.
I almost kind of wonder if the reason it did that is
because I asked about that for earlier question,
which would be really cool.
So yeah, we could see that actually just works.
But what if we wanted it to be in Java?
Could you give me Java code instead?
Right? So that's one thing that could be super cool
for sort of applications of Chat GPT
as you could have written code in one language
and maybe you want it to be in another language
because of affordability reasons
or whatever reason that you may want.
And if you ask Chat GPT to like
kind of generate the same code for
that problem spec in a different language.
It's probably able to do that
And let's actually verify if it did it correctly.
Once again, it incorrectly annotated the type
or the code block here.
But as long as you are familiar with coding languages,
in fact let's actually run an experiment on that.
I mean it's referencing this as Java code,
but in case you really didn't know,
you could probably try copying this code
and then asking it what language is this written in?
And it should probably say Java.
cause I mean that's what it looks like, right?
But without further delay, let's just copy that
straight into Java, the Java code pen here,
and let's submit that, see if it works.
Sure enough, it is a correct solution once again.
So that's really cool, right?
Like you can translate between the two languages here,
more or less using the same algorithm here.
But yeah, that just really shows the power
of Chat GPT in algorithms
and look forward to seeing you
in the next video about debugging.