Here is a paranoid algorithm to compute the maximum of a set A of n real...

 

Transcribed Image Text:

Here is a paranoid algorithm to compute the maximum of a set A of n real numbers: Algorithm ParanoidMaximum (A) 1. if card (A) = 1 then 2. 3. 4. 5. 6. 7. 8. return the unique element x = A else Pick a random element x from A. ParanoidMaximum (A\{x}) X' if x x' then return x' else Now we suspect that x is the maximum, but to be absolutely sure, we compare x with all card (A) - 1 other elements of A (and set x to be the maximum of A\{x}). return x What is the worst-case running time of this algorithm? What is the expected running time (with respect to the random choice in line 3)? Activate W Go to Setting Here is a paranoid algorithm to compute the maximum of a set A of n real numbers: Algorithm ParanoidMaximum (A) 1. if card (A) = 1 then 2. 3. 4. 5. 6. 7. 8. return the unique element x = A else Pick a random element x from A. ParanoidMaximum (A\{x}) X' if x x' then return x' else Now we suspect that x is the maximum, but to be absolutely sure, we compare x with all card (A) - 1 other elements of A (and set x to be the maximum of A\{x}). return x What is the worst-case running time of this algorithm? What is the expected running time (with respect to the random choice in line 3)? Activate W Go to Setting