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.

4. Consider the following function: func4(A, n) /* A is an array of integers is 0; 2 k + Random(n); 3 if (k