Write the recurrence equation for the code below. Use the number of comparisons as your barometer operation $($The min operation requires $1$ comparison and the max operation requires $1$ comparison$)$: $)$: $($Note: you can count min and max as the comparison operation and skip the rt$-$lt $<=1)$

MinMax$($A$,$lt$,$rt$)$

$//$ return a pair with the minimum and the maximum

if $($rt $-$ lt $1)$

return $($min$($A$[$lt$],$ A$[$rt$]),$ max$($A$[$lt$],$A$[$rt$]))$;

$($min$1,$ max$1)=$ MinMax$($A$,$lt$,($lt$+$rt$)/2)$;

$($min$2,$ max$2)=$ MinMax$($A$,($lt$+$rt$)/2+1,$rt$)$;

return $($min $($min$1,$ min$2),$ max$($max$1,$ max$2))$;

Show the recursion tree and solve the recurrence equation for this code. For simplicity assume n $=2$k$.$

Prove the solution using induction.