Consider the recurrence:

$T(n)=\{\begin{array}{ccc}9T(\frac{n}{3})+O(n^2)& \text{f}\text{o}\text{r}& n>1\\ 1& \text{f}\text{o}\text{r}& n=1\end{array}$

Solve the recurrence to find a tight upper bound using the substitution method.

Consider the following divide$-$and$-$conquer algorithm:

float myFunc$($X$)\{$

n $=$ X$.$length;

if $($n $==1)\{$

return X$[0]$;

$\}$

$//$ let X$1,$ X$2$ be arrays of size n$/2$

for $($i $=0$; i $!=($n$/2)-1$; i$++)\{$

X$1[$i$]=$ X$[$i$]$;

X$2[$i$]=$ X$[$n$/2+$ i$]$;

$\}$

for $($i $=0$; i $!=($n$/2)-1$; i$++)\{$

for $($j $=0$; j $!=($n$/2)-1$; j$++)\{$

if $($X$1[$i$]==$ X$2[$j$])\{$

X$2[$j$]=0$;

$\}$

$\}$

$\}$

r$1=$ myFunc$($X$1)$;

r$2=$ myFunc$($X$2)$;

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

$\}$

$($a$)$ Obtain a recurrence relation for the algorithm's basic operation count.

$($b$)$ Solve the recurrence relation found in part $($a$)$ to find a tight bound. Please use the proper

asymptotic notation to state the tight bound.

Note: You don't need to consider what the algorithm computes; just focus on the basic

operations.