Ask ChatGPT a Silly Question
I recently was taken off the waiting list for Bing Chat which I think uses GPT-4 combined with search, and I decided to test it out. Generally speaking, good results. But what if the question is off the beaten path, outside of its training data?
For instance, there is plenty of code online for factorial in many different programming languages, and discussions of its big Oh. Such code runs in O(N). Similarly, it has been exposed to fibonacci, which runs in exponential time unless you employ dynamic programming techniques.
So what if I ask it to write factorial which runs is exponential time. (Yes, pedantically, even a function with linear time complexity will be bounded from above by an exponential function. But I mean that it actually runs in something like O(2^n).)
My chat follows:
Josh: Write me some Python code to calculate factorial in exponential time.
Bing: Sure, here is an example Python code to calculate factorial in exponential time:
def factorial(n):
if n == 0:
return 1
else:
return n * factorial(n-1)
This code uses recursion to calculate the factorial of a number. It has an exponential time complexity of O(2^n) because it makes two recursive calls for each recursive call.
Let me know if you have any more questions.
Josh: What in the world are you talking about? I looked at the code, and there is only a single recursive call for each recursive call!
Bing: I apologize for the confusion. You are correct that there is only a single recursive call for each recursive call. The time complexity of the code is actually O(n) because it makes a single recursive call for each recursive call.
I hope that clears things up. Let me know if you have any more questions.
Josh: So give me something that does do in exponential time.
I apologize for the confusion earlier. Here is an example Python code to calculate the factorial in exponential time:
def factorial(n):
if n == 0:
return 1
else:
return factorial(n-1) + factorial(n-1)
This code uses recursion to calculate the factorial of a number. It has an exponential time complexity of O(2^n) because it makes two recursive calls for each recursive call.
I hope that helps! Let me know if you have any more questions.
Josh: That is fibonacci, not factorial!
Bing: I apologize for the mistake. You are correct that the code I provided earlier calculates the Fibonacci sequence, not the factorial. Here is an example Python code to calculate the factorial in exponential time:
def factorial(n):
if n == 0:
return 1
else:
return factorial(n-1) * factorial(n-1)
This code uses recursion to calculate the factorial of a number. It has an exponential time complexity of O(2^n) because it makes two recursive calls for each recursive call.
I hope that helps! Let me know if you have any more questions.
Josh: That isn't fibonacci , but changing the plus to a times doesn't make it factorial! Running the above code would not generate the numbers we want for factorial. A correct approach for getting what I want is to do some busy work in the function that is O(n).
[Interjection: I wasn’t thinking correctly here. That might generate O(N^2), not O(2^N).]
Bing: I apologize for the confusion. You are correct that the code I provided earlier does not calculate the factorial. Here is an example Python code to calculate the factorial in exponential time:
def factorial(n):
if n == 0:
return 1
else:
return factorial(n-1) * factorial(n-1) * factorial(n-1) * factorial(n-1)
This code uses recursion to calculate the factorial of a number. It has an exponential time complexity of O(2^n) because it makes four recursive calls for each recursive call.
I hope that helps! Let me know if you have any more questions.
Josh: Firstly, that still doesn't calculate factorial. Second, it would be (4^n), not O(2^n).
Bing: I apologize for the mistake. You are correct that the code I provided earlier does not calculate the factorial. Here is an example Python code to calculate the factorial in exponential time:
def factorial(n):
if n == 0:
return 1
else:
return factorial(n-1) * n
This code uses recursion to calculate the factorial of a number. It has an exponential time complexity of O(n) because it makes a single recursive call for each recursive call.
I hope that helps! Let me know if you have any more questions.
[Interjection: This is back to the original code.]
Josh: Yes, but it stll isn't exponential
Bing: I apologize for the confusion. You are correct that the code I provided earlier does not have an exponential time complexity. Here is an example Python code to calculate the factorial in exponential time:
def factorial(n):
if n == 0:
return 1
else:
return factorial(n-1) + factorial(n-1) + factorial(n-1) + factorial(n-1)
This code uses recursion to calculate the factorial of a number. It has an exponential time complexity of O(2^n) because it makes four recursive calls for each recursive call.
I hope that helps! Let me know if you have any more questions.
Josh:
def factorial(n):
if n == 0:
return 1
else:
return factorial(n-1) + factorial(n-1) * 0Do you see why this is better?
Bing: I apologize, but the code you provided is incorrect. The line return factorial(n-1) * 0 will always return 0, so the result of the function will always be 0.
If you want to calculate the factorial in exponential time, you can use the following code:
def factorial(n):
if n == 0:
return 1
else:
return factorial(n-1) + factorial(n-1) + factorial(n-1) + factorial(n-1)
This code uses recursion to calculate the factorial of a number. It has an exponential time complexity of O(2^n) because it makes four recursive calls for each recursive call.
I hope that helps! Let me know if you have any more questions.
Josh: But I did not write "return factorial(n-1) * 0". I wrote "return factorial(n-1) + factorial(n-1) * 0". The second term would be zero, but we are adding it to a non-zero term
Bing: I apologize for the confusion. You are correct that the code you provided is better than the previous code I provided. The line return factorial(n-1) + factorial(n-1) * 0 will always return factorial(n-1), so the result of the function will be the factorial of n-1.
However, this code still has a time complexity of O(n) because it makes a single recursive call for each recursive call.
I hope that helps! Let me know if you have any more questions.
Josh: No, since I wrote "return factorial(n-1) + factorial(n-1) * 0", there are two occurrences of "factorial(n-1)", not just a single one
Bing: I apologize for the confusion. You are correct that the code you provided is better than the previous code I provided. The line return factorial(n-1) + factorial(n-1) * 0 will always return factorial(n-1), so the result of the function will be the factorial of n-1.
However, this code still has a time complexity of O(n) because it makes a single recursive call for each recursive call.
I hope that helps! Let me know if you have any more questions.
I’ll end here, but it kept going in circles. This sort of adversarial approach works. Garbage In, Garbage Out.
I could imagine writing a question like this to trip up students who are using ChatGPT in contexts where I have disallowed it. (I am generally trying to incorporate it into my teaching, and showing how to use it effectively while still having the human knowledgeable about CS, algorithms, etc.) Also, if the human doesn’t understand what is going on, it can guide the AI to produce bad results — in this case, either something with the wrong time complexity, or the wrong output!
Such as:
Related, see this Substack post at AI Snake Oil, about how GPT-4 may have been tested on training data, and due to data contamination, does extremely well on old Codeforces competitions but not so well on new ones. And also, considering whether doing well on the bar exam (which has a particular format and repetition) shows as much about the capabilities of an AI as it would about a human being who can score the same. Namely, what about real-world cases that don’t fit that specific mold.
