Q$\mathrm{.}1.(25$ points$).($COl$-$Algorithm complexity$)$

int algorithm $($int $N)$

int sum $=0$

$if(N=0)$

return $0$;

$CO2$Q$\mathrm{.}2.(25$ points$)($CO$2-$Master Theorem$)$ Solve the following recurrences by giving tight $-$

notation bounds. You need to justify your answers.

$($a$)T(n)=3T(\frac{n}{5})+l{g}^{2}n$

$($b$)T(n)=2T(\frac{n}{3})+nlgn$

$($c$)T(n)=T(\frac{n}{5})+l{g}^{2}n$

$($d$)T(n)=-8T(\frac{n}{2})+n^3$

$($c$)T(n)=7T(\frac{n}{2})+n^3$

Q$\mathrm{.}3.(25$ points$)(CO3-$ Brute Force$)$

Write a brute force algorithm to find the closest pair in k$-$dimensional plane. Assume that there

are $n$ distinet points. Determine the time complexity of this algorithm.