Write a recurrence relation describing the worst casc running time of cach of the following algorithms and determine the asymptotic complexity of the function defined by the recurrence relation. Justify your solution using either substitution, a recursion tree or induction. You may NOT use the Master theorem. Assume that all arithmetic operations take constant time. Simplify and express your answer as (nk) or (nk(log n)) wherever possible. If the algorithm takes exponential time, then just give exponential lower bounds. func9(A,n) A = array of integers 1 if (n-20) then return A[1]; 2 for i 1 to Ln/2] do B[i] Ali] + Ali + 1]; 5 end s return (r)