Consider the following two recursive algorithms for computing the

largest element in an array. For each algorithm let T$($n$)$ denote the running time on an array of

size n$.$ For each one of them, set up recurrence relation for the running time T$($n$)$ and solve it to

get the asymptotic running time complexity.

FindLargest$1($A$[$n$])$:

if n $=1$: return A$[1]$;

else

mid $=$ n$/2$;

largest $=$ FindLargest$1($A$[1,..,$mid$])$

if largest $$ FindLargest$1($A$[$mid$+1,..,$n$])$

largest $=$ FindLargest$1($A$[$mid$+1,..,$n$])$;

return largest;

FindLargest$2($A$[$n$])$:

if n $=1$: return A$[1]$;

else

mid $=$ n$/2$;

largest $=$ FindLargest$2($A$[1,..,$mid$])$

otherLargest $=$ FindLargest$2($A$[$mid$+1,..,$n$])$

if largest $$ otherLargest

largest $=$ otherLargest;

return largest;Question $1(4$ points$)$: Consider the following two recursive algorithms for computing the

largest element in an array. For each algorithm let $T(n)$ denote the running time on an array of

size $n.$ For each one of them, set up recurrence relation for the running time $T(n)$ and solve it to

get the asymptotic running time complexity.

FindLargest$1($A$[$n$])$:

if $n=1$ : return $A[1]$;

else

mid$=\frac{n}{2}$;

largest $=$ FindLargest$1,$ mid