Data: String $T$ with $n$ lowercase letters

Result: The number of palindrome substrings in string $T$

clarr$0$;

for ilarr$0$ to $n-1$ do

for jlarri to $n-1$ do

substring to $j$;

if isPalindrome$($substring$)$ then

clarrc$+1$

end

end

end

return $c$

$($a$)$ Prove that this algorithm is correct by providing the following:

i$.(2$ marks$)$ Show that the algorithms terminates.

Note: To prove that the algorithm terminates you cannot just give an example and show that the algorithm terminates on it; instead you must prove that when the algorithm is given any input string of length $n,$ for any value of $n,$ the algorithm will always end.

ii$.(2$ marks$)$ Show that the algorithm always produces the correct answer.

Note: To prove that the algorithm is correct you cannot just give an example and show that the algorithm computes the correct output. You must prove that when the algorithm is given any input string of length $n1,$ the algorithm correctly outputs the number of palindromes in the string. Assume that the function isPalindrome$()$ always produces correct output.

iii. $(4$ marks$)$ Compute the time complexity of this algorithm in the worst case. You must explain how you computed the time complexity, and you must give the order of the complexity. Assume that the function isPalindrome$()$ takes only a constant time to execute.