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.

1. Consider the following function: func1(A, n) /* A is an array of integers 1s+ 0; 2 kr Random(n); 3 for it 1 to k do 4 for j - 1 to [k1/3] do 5 s ts + A[i] * A[j]; 6 end 7 end 8 return (s); (a) What is the asymptotic worst case running time of funci? (b) What is the asymptotic expected running time of funci? 1. Consider the following function: func1(A, n) /* A is an array of integers 1s+ 0; 2 kr Random(n); 3 for it 1 to k do 4 for j - 1 to [k1/3] do 5 s ts + A[i] * A[j]; 6 end 7 end 8 return (s); (a) What is the asymptotic worst case running time of funci? (b) What is the asymptotic expected running time of funci