The following algorithm uses a divide$-$and$-$conquer technique to find the maximum element in an array of size n$.$ The initial call to this recursive function is max$($arrayname$,0,$ n$).3$ dtype Findmax$($dtype A$[],$ int i$,$ int n$)\{//$i is the starting index, and n is the number of elements. dtype M ax$1,$ M ax$2$; if $($n $==1)$ return A$[$i$]$; M ax$1=$ Findmax $($A$,$ i$,$ bn$/2$c$)$; $//$Find max of the first half M ax$2=$ Findmax $($A$,$ i $+$ bn$/2$c$,$ dn$/2$e$)$; $//$Find max of the second half if $($M ax$1$ M ax$2)$ return M ax$1$; else return M ax$2$; $\}$ Let f$($n$)$ be the worst$-$case number of key comparisons for finding the max of n elements. $($a$)$ Assuming n is a power of $2,$ write a recurrence relation for f$($n$).$ Find the solution by each of the following methods. i$.$ Apply the repeated substitution method. ii$.$ Apply induction to prove that f$($n$)=$ An $+$ B and find the constants A and B$.($b$)$ Now consider the general case where n is any integer. Write a recurrence for f$($n$).$ Use induction to prove that the solution is f$($n$)=$ n $1.$