Question

Let T(n) be the runtime of the following isPalindrome() method which accepts a string of length n: public boolean isPalindrome(String str) { if (str.length() < 2) return true; if (str.charAt(0) != str.charAt(str.length()-1)) return false; return isPalindrome(str.substring(1, str.length()-1)); } Assuming each line of code (like each semicolon) counts as one instruction, choose the most appropriate recurrence that describes the runtime of isPalindrome(). Select one: a. T(n) = 3n + T(n-2), T(1) = 1, T(0) = 1

b. T(n) = 3n + T(n-1) , T(1) = 1, T(0) = 1

c. T(n) = 3 + T(n-2), T(1) = 1, T(0) = 1

d. T(n) = 3 + 2T(n-1), T(1) = 1, T(0) = 1

e. T(n) = 3 + T(n-1), T(0) = 1

Answer 1

Ans: c). T(n) = 3 + T(n-2), T(1) = 1, T(0) = 1

=============================

First let's check our base case:

if (str.length() < 2) return true;

So for T(0) as well as T(1) we only execute one instruction. So they are equal to 1.

Now, for some n > 2 we check the first and last character and pass the remaining string of length n-2 as input for next function call. Also in this process we executed 3 statements.

So T(n) = 3 + T(n-2)

T(n-2) is term for the next call to isPalindrome with substring from 1 to n-1 passed. 3 is the term for the 3 statements executed.

hence option c is correct and remaining are incorrect.

========================

for any query comment