Write a recurrence relation describing the WORST CASE running time of each of the following algorithms. Justify your solution with either substitution, a recursion tree, or induction. Simplify your answer to (n^k ) or (n^k log(n)) whenever possible. If the algorithm takes exponential time, then just give exponential lower bounds.

1: function Func(A[],n) 2: if n