This is definitely a stupid, and simple question. But for some reason this is bugging me. This is not a homework question–insofar, as I am not solving a homework question for my own work. I am a mathematician, who’s helping his friend with some of his math homework for his CS degree. And I am pretty certain I have the correct solution, but ChatGPT gives a different solution. And he wants to follow ChatGPT’s solution, when I’m pretty sure it is wrong.
The pseudo code is simple
l=0
while n >= 1 do
for j=1, n, do
l = l+2
od
n = n/3
od
ChatGPT has said that this is O(n^2 log(n)), and that just doesn’t make sense to me. It’s explanation is also kind of nonsense. But my friend seems to be leaning toward ChatGPT, which I think is bull shit. I believe the correct bound is O(nlog(n)), and I’ve supplied the following reasoning.
The operation:
while n >= 1 do
n = n/3
od
grows likes O(log(n). The act of adding a for loop, as the one I used, looks like:
Sum_{j=1}^{log(n)} O(n/3^j)
This entire sum of operations, just becomes O(nlog(n))…
I’m pretty confident ChatGPT is wrong in this scenario, but I’d appreciate someone more well versed in this kind of stuff. I don’t translate code to O notation at all in my work. If I’m wrong that’s fine, but I’d appreciate a well thought out answer. For god’s sakes, this program has me checking my sanity!
>Solution :
You are right. ChatGPT is wrong. Your logic is sound. You’ve got an O(n) operation nested inside an O(log n) operation, which comes out to O(n * log n).
This should not come as a surprise: ChatGPT is designed to write prose, and has a consistent track record of making a very convincing case for "facts" and solutions that are simply wrong. Your friend should get out of the habit of relying on ChatGPT for their homework answers for this reason, even if they’re ignoring the ethics of the matter.