I'm doing an online course with the following multiple choice question:
where the RANDOMIZED SELECT algorithm (based on quicksort) is described as follows:
Since all the multiple choice options are linear functions of a (by which I mean the Greek letter alpha), I'm trying to determine the correct answer by elimination by considering the limiting cases a = 0.5 and a = 1.
Now if a = 1, we are looking for "the probability that after the first iteration the size of the subarray in which the element you are looking for is <=1 times the size of the original array". It would seem to me that this is always true, since one iteration always reduces the problem size, so the probability should be 1.
If I'm correct about this, this leaves only one possible correct answer, 2 a - 1. However, if I fill in a = 0.5 into this expression I get zero, which does not make sense to me: it would mean it is impossible for the problem size to be less than half the original problem size after one iteration.
In short, none of these answers seem correct to me; can someone point out the flaw in my reasoning?
Aucun commentaire:
Enregistrer un commentaire