$4.$ Consider the following algorithm for the problem of counting the number of palindromes in a given string $\backslash ($ T $\backslash )$ of length $\backslash ($ n $\backslash$geq $1\backslash ).$ The function isPalindrome$()$ takes a string input and return True if the input string is a palindrome and False otherwise.

Data: String $\backslash ($ T $\backslash )$ with $\backslash ($ n $\backslash )$ lowercase letters

Result: The number of palindrome substrings in string $\backslash ($ T $\backslash )\backslash ($ c $\backslash$leftarrow $0\backslash )$;

for $\backslash ($ i $\backslash$leftarrow $0\backslash )$ to $\backslash ($ n$-1\backslash )$ do

for $\backslash ($ j $\backslash$leftarrow i $\backslash )$ to $\backslash ($ n$-1\backslash )$ do

substring $\backslash (\backslash$leftarrow T$[$i $\backslash )$ to $\backslash ($ j$]\backslash )$;

if isPalindrome$($substring$)$ then $\backslash ($ c $\backslash$leftarrow c$+1$ ; $\backslash )$

end

end

end

return $\}$

$($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 $\backslash ($ n $\backslash$geq $1\backslash ),$ 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.