Write a recurrence relation describing the worst case running time of each of the following algorithms and determine the asymptotic complexity of the function de ned 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.

func5(A,n) /* A = array of n integers */ 1 if (n <= 20)then return A[1]; 2 x = 0; 3 for i = 8 to n - 6 do 4 A[i] = A[i] + A[i + 2]; 5 x = x+func5(A, i); 6 end 7 return (x);