4. (15 pts.) A common operation in many computer simulations is the generation of samples from a discrete random variable. The problem essentially can be mathematically reduced to the following simple case. Consider a discrete random variable x taking values in the set Sx = {0,1,2,...,n-1 with probability mass function (PMF) px, so that Px() is the probability that the random variable X takes value xe Sx. Let Fx be the cumulative distribution function (CDF) of X, whose domain is the set of real values R = (-0, +00), and is defined as Fx (x) = P(XS) = if : n-1. A simple general approach to generate random samples from X according to its PMF PX is to draw a number r uniformly at random from the interval (0,1), and then use the CDF FX to select the value x as the random sample of X if Fx (x - 1) Sr F[2] do 10: 2+1 11: return Algorithm 2 RANDDISCRETE2(P) 1: F new n-element array 2: F0 - PO 3. for 3 + 1 to n - 1 do 4: Flui Flj - 1] +PG] 5: T + RANDO 6: 10 7: while r > F[x] do 8: + 2+1 9: return (a) Give the tightest running-time and space characterization using big-Oh and big-Omega, or big-Theta, of RAND DISCRETEI in terms of n. Briefly justify your answer. Time Space (b) Give the tightest running-time and space characterization using Big-Oh and Big-Omega, or Big-Theta, of RAND DISCRETE2 in terms of n. Briefly justify your answer. Time Space (c) Which algorithm do you recommend to implement, and why? Briefly justify your answer. (d) Write, in pseudocode, a linear-time algorithm RAND DISCRETE3 for this computational problem that takes an array P of n elements as input and outputs a random integer consistent with a discrete random variable with integer values 0,1,...,-1 according to the probability mass function encoded by P and that uses a constant amount of space. Is this algorithm better than the algorithm you recommended to implement in the previous part of this problem? Please explain briefly