Directions: 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.)

1. Consider the following function: funci(A, n) /* A is an array of integers i if n