what is the time complexity of an algorithm that recursively checks if a string is a palindrome?

I have solved the problem using this algorithm and have calculated that the total number of recursive calls is n/2 since we always pass a substring of the original string with 2 less characters. The runtime complexity of the slice() function is O(n). If there are n/2 function calls and in each one we call the slice function taking O(n) time, wouldn't the time complexity of this algorithm be O(n/2 * n) or O(n^2)?

function checkIfPalindrome(string) {
  const leftMost = string[0],
    rightMost = string[string.length - 1];
  //base case 1: if length of original string is an odd number, then this base case applies
  if (string.length === 1) return true;

  //base case 2: if length of original string is an even number, then this base case applies
  if (string.length === 2) {
    if (leftMost === rightMost) return true;
    else return false;
  }

  //check if leftmost char === rightmost character
  //if true, continue recursive process, else return false;
  if (leftMost !== rightMost) return false;

  return checkIfPalindrome(string.slice(1, string.length - 1));
}

I ran the code through chatGPT and it said the Big O notation for this is O(n) but I am taking that with a grain of salt.

Solution

I have solved the problem using this algorithm and have calculated that the total number of recursive calls is n/2 since we always pass a substring of the original string with 2 less characters. The runtime complexity of the slice() function is O(n). If there are n/2 function calls and in each one we call the slice function taking O(n) time, wouldn't the time complexity of this algorithm be O(n/2 * n) or O(n^2)?

Yes, your reasoning and conclusion are correct. The time complexity is O(n²) = O(n²/2) = O(n/2 * n). The first of those is the conventional expression and probably the one that your grader would prefer, but all are technically correct.

I ran the code through chatGPT and it said the Big O notation for this is O(n)

Which tells you that you would be better off not consulting ChatGPT on your homework questions. It only confused you this time, but if you had come to the wrong conclusion on your own then it might have affirmed your incorrect answer. ChatGPT is trained to produce responses that will be of about the right form, but it isn't particularly good at getting answers that are correct, especially for questions that hinge on details.

From ChatGPT itself:

You

How reliable are ChatGPT's answers?

ChatGPT

As an AI Language Model, I strive to provide the most accurate and relevant information to the best of my abilities. However, ChatGPT's answers may not always be 100% accurate or appropriate for every situation or person. It is essential to consider the sources of the information I provide and use your judgment when making decisions based on my responses. In critical situations or cases where accuracy is crucial, it is best to consult with a qualified expert in the particular field.