For the following questions, simplify and express your answer as (n^k ) or (n^k (log n)) wherever possible (showing an explicit value of k). If the 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 1 and n is equally likely.)

4. Consider the following function: Input : Array A of at least j elements. Integers i and j. Result : A permutation of the i through j elements of A such that Ail