Let 0<α<1 be a constant, independent of n. Consider an execution of RSelect in which you always manage to throw out at least a 1−α fraction of the remaining elements before you recurse. What is the maximum number of recursive calls you'll make before terminating?
−log(n)log(1−α)
−log(n)α
−log(n)log(12+α)
−log(n)log(α)