Consider the function below to reverse the substring of $S$ from position $i$ to $j.$

If S were defined as a string "abcdefg" then

reverseString $(S,0,$ len$($S$)-1)$ function would return "gfedcba"

reverseString $(5,3,4)$ function would return "abcedfg"

Function in pseudocode:

reversestring $($S$,$ int $i,$ int $j)$

if $(=S[i]S[i]=S[j]s[j]=i+1,j-1ST(n)=k+2**T(n-1)$

$T(n)=k+T(n-2)T(n)=k+T(n-1)$

$T(n)=k+ni$

temp $=S[i]$

$S[i]=S[j]$

$s[j]=$ temp

return reversestring $(S,i+1,j-1)$

else

return $S$

What $is$ the recurrence relation $of$ reversestring?

$T(n)=k+2**T(n-1)$

$T(n)=k+T(n-2)$

None $of$ the other answers are correct

$T(n)=k+T(n-1)$

$T(n)=k+n$