$4)$ Recursive Analysis

HomeworkUnanswered

The following algorithm takes an unsorted list of positive integers, along with two integers and $.$It returns the largest number, $,$ in the list such that either or is true. $$It returns $0$ if no such exists. $$The algorithm assumes that the list size, $,$ is a power of $2$ with $.($Recall that the function is known as floor and might be written in text mode as floor$($x$).)$

$1$ : integer xyMax$($x$,$ y$,\{$a$\_0,$ a$\_1,...,$ a$\_\{$n$-1\}\})2$ : if n $==13$ : if $($a$\_0^$x $==$ y$)$ or $($a$\_0^$y $==$ x$)4$ : return a$\_05$ : else $6$ : return $07$ : $8$ : # process the left half $9$ : $10$ : m$\_1=$ xyMax$($x$,$y$,\{$a$\_0,...,$ a$\_\{$floor$($n$/2)-1\}\})11$ : $12$ : # process the right half $13$ : $14$ : m$\_2=$ xyMax$($x$,$y$,\{$a$\_\{$floor$($n$/2)\},...,$ a$\_\{$n$-1\}\})15$ : $16$ : # find the largest $17$ : $18$ : max $=$ m$\_119$ : if $($m$\_2>$ max$)20$ : max $=$ m$\_221$ : $22$ : return max $23$ : end xyMax

What is the recurrence relation that counts the number of comparisons for this algorithm?

What is a good big$-$ reference function for algorithm xyMax? $($Hint: $$Which Master Theorem applies here?$)$