Consider the following algorithm for the problem of counting the num$-$

ber of palindromes in a given string $T$ of length $n1.$ The function

isPalindrome$()$ takes a string input and return True if the input string

is a palindrome and False otherwise.

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 cor$-$

rect output. You must prove that when the algorithm is given

any input string of length $n1,$ the algorithm correctly out$-$

puts 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 com$-$

plexity, and you must give the order of the complexity. Assume

that the function isPalindrome$()$ takes only a constant time to

execute.