7. (20 points) Compute the expected running time of the following randomized alg

Question

7. (20 points) Compute the expected running time of the following randomized algorithm that re turns a random permutation for a given array A[1..nl of distinct integers. (The symbol := is the assignment operator and the symbol = is the equality operator.) Input: An array A[1..n] of distinct integers. Output: A random permutation C[1..n] of A. (1:) Set B[1..m] := {FALSE,. .. ,FALSE} (2:) Set i := 1 (3:) Generate a random number j in [1, .. . , m} (4:) If B[jl = FALSE then do du := A[j], j := j + 1, B[j] : TRUE (5:) Repeat steps (3:) and (4:) until j = n + 1. (6:) Return C as a random permutation of A.

Explanation / Answer

Expected running time is same as average running time.

Let me convert step 2-5 into actual pseudo kind of code:

int i = 1;

while (i < n +1)

{

random j = new random(1,n);

if (B[j] == false)

{

C[i] = A[j];

i = i + 1; // note that i will only incremented within this if condition

B[j] = true;

}

}

return C;

You can see clearly that there is only one loop (running time determining step). So expected running time will be linear. In terms of big O notation, it will be O(n).

Related Questions

Navigate

• Browse (All)
• Browse 7
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.