For each of the following problems, provide a clear justification for your solution.

Wherever possible, simplify and express your answer as (n^m) or (n^m(log n)) (showing an explicit value for m).

In problems where you can show an exponential lower bound, you do not need to give a matching upper bound.

Random(n) generates a random number between 1 and n with uniform distribution (every integer between 1 and n is equally likely.) CoinFlip() returns heads or tails with equal probability.

2. Consider the following function: func2(A, n) /* A is an array of integers 18+ 0; 2 for it1 to n do k + Random(i); for j+1 to k do | for m + 1 to k0.2 do sts+ Ali] * A[j] * Am]; end 8 end 9 end 10 return (s); (Random(i) generates a random number between 1 and i with uniform distribution (every integer between 1 and i is equally likely.) (a) What is the asymptotic worst case running time of func2? (b) What is the asymptotic expected running time of func2? (Hint: Construct the expected running time of steps 3-8 as a function of i and then apply linearity of expectation.) 2. Consider the following function: func2(A, n) /* A is an array of integers 18+ 0; 2 for it1 to n do k + Random(i); for j+1 to k do | for m + 1 to k0.2 do sts+ Ali] * A[j] * Am]; end 8 end 9 end 10 return (s); (Random(i) generates a random number between 1 and i with uniform distribution (every integer between 1 and i is equally likely.) (a) What is the asymptotic worst case running time of func2? (b) What is the asymptotic expected running time of func2? (Hint: Construct the expected running time of steps 3-8 as a function of i and then apply linearity of expectation.)