Problem $2.[$Category: Analyzing Recursive Algorithms$]$ Consider the algorithm

FunSort$($A$[1..$n$])$

if n $>1$ then

m $$ n

$2$

for i $1$ to m do

for j $$ m $+1$ to n do

if A$[$j$]<$ A$[$i$]$ then

A$[$i$]$ A$[$j$]$

end if

end for

end for

end if

FunSort$($A$[1..$m$])$

FunSort$($A$[$m $+1..$n$])$

$1.$ Write a recurrence for this algorithm$$s running time. $($you do not need to argue for it$.)[15$ points$]$

$2.$ Use the Master Theorem to solve the above recurrences, so as to express the running time in the form

$($f $($n$))$ or O$($f $($n$))$ where f should be as simple as possible. $[5$ points$]$