Write a recurrence relation describing the worst case running time of each the following

algorithms and make a guess about the asymptotic complexity of the functions defined by

the recurrence relation using either expanding into a series or a recursion tree.

$A[idotsj]$ represents an array of $n=j-i+1$ numbers starting at index i and ending at

index $j$ and $A[k]$ represents the value at index $k.$

$1.)$ FUNCTION $F_1(A[1$dotsn$])$

IF $n5$ THEN RETURN$(A[n])$

xlarr$0$

FOR ilarr$1$ TO $5$ DO

BEGIN $($FOR $i)$

FOR jlarr$1$ TO $n-4$ DO

$A[i]larrA[j]+A[j+2]$

xlarrx$+F_1(A[1$dots${|}_{{?}_{?}}\frac{n}{2_{{?}_{?}}}|])$

END

RETURN $(x)$

$2.)$ FUNCTION $F_2(A[idotsj])$

nlarrj$-i+1$

IF $n1$ THEN RETURN $(A[i])$

$xlarr{F}_2(A[idots{|}_{{?}_{?}}i+2\frac{n}{3_{{?}_{?}}}|])$

FOR ilarr${|}_{{?}_{?}}\frac{n}{4_{{?}_{?}}}|$ TO ${|}_{{?}_{?}}\frac{n}{4_{{?}_{?}}}|+12$ DO

xlarrx$+A[i]$

RETURN $(x)$

$3.)$FUNCTION $F_3(A[1$dotsn$])$

$IFn1$ THEN RETURN $(A[1])$

FOR ilarr$1TOnDO$

FOR jlarr$1TO{|}_{{?}_{?}}\frac{n}{3_{{?}_{?}}}|DO$

$,A[i]larrA[i]-A[j]$

$xlarr{F}_3(A[1..{|}_{{?}_{?}}3\frac{n}{5_{{?}_{?}}}|])$

RETURN$(x)$