For each of the following problems, simplify and express your answer as (nk) or (nk(log n)) wherever possible. If the asymptotic running time is exponential, then just give exponential lower bounds. Random(n) generates a random number between 1 and n with uniform distribution (every integer between I and n is equally likely.)