GATE Overflow Test Series | Data Structures | Test 1 | Question: 12

Question

The time complexity of the below code is

int isPalindrome ( char * string, int n )
{
    if (n <= 1) return 1;
    if (string[0] != string[n-1]) return 0;
    return isPalindrome(string + 1, n-2);
}

 

• A. $\Theta(n)$
• B. $\Theta (n \log n)$
• C. $\Theta(\log n)$
• D. $\Theta(n^2)$

Answer 1

There is maximum $n$ recursive calls and each is of $O(1).$ So, total time complexity is $O(n).$

PS: The above code is not optimal in the sense that each characters at positions $i$ and $n-i-1$ are compared with each other twice.

Comments

What would be the recurrence relation for the number of calls?

---

T(n) = T(n-2) + c

Is this the correct recurrene relation for the above function?

---

same doubt

---

can anyone provide an answer to this