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!

CodePudding user response：

Update

I realize I may have spoken too soon to say whether O(n * log n) is the right answer. It's certainly a lot closer to a right answer than O(n² * log n).

Original answer

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.

CodePudding user response：

This question was answered by @moreON but I will present the answer properly, as I see it. Thank you @StriplingWarrior, you definitely quenched my fears that I was so off. I knew it was at least O(n log(n)), but the correct answer is O(n). Which you identified before me, after @moreON's comments.

The program f which takes n and gives l is given as:

l = 0
while n >=1 do
   for k=1, k <= n, do
       l = l 2
   od
   n = n/3
od

The time it takes to run this program, if we treat each single operation as O(1)--looks exactly like the equation:

sum_{i=1}^{log_3(n)} n/3^i

When we consider the growth in n. This comes about from the while loop doing about log_3(n) loops. From here, we do a while loop for at least 1 <= m = n/3. This does, for each term in the log_3(n) list, a larger division by three, n/3^i. We can write the growth in cpu time to evaluate n of f

sum_{i=1}^{log_3(n)} n/3^i = n O(1)

As a mathematician I should've seen this. But even if I did, I'd doubt that it's that easy. Or as simple as that. Just a bound on a relatively simple sum. I thought, at best we can rough bound it with O(nlog n). But, we can prove that the solution to our problem is:

f(n) = O(n)

I want to thank @moreON and @StriplingWarrior. You guys were right... I apologize for being a jack ass.