Problem:
Let $ 0 < \alpha < 1 $ be a constant, independent of $ n $. Consider an execution of RSelect in which you always manage to throw out at least a $ 1 - \alpha $ fraction of the remaining elements before you recurse. What is the maximum number of recursive calls you'll make before terminating?
Solution:
In the initial call, we have $ n $ elements.
In the first recursive call, we have at most $ \alpha n $ elements.
...
In the dth recursive call, we have at most $ \alpha^d n $ elements.
If the recursion has to stops at the dth recursive call, then $ \alpha^d n \le 1 $, that log on both side we get
$ d = -\frac{\log n}{\log \alpha} $.
Let $ 0 < \alpha < 1 $ be a constant, independent of $ n $. Consider an execution of RSelect in which you always manage to throw out at least a $ 1 - \alpha $ fraction of the remaining elements before you recurse. What is the maximum number of recursive calls you'll make before terminating?
Solution:
In the initial call, we have $ n $ elements.
In the first recursive call, we have at most $ \alpha n $ elements.
...
In the dth recursive call, we have at most $ \alpha^d n $ elements.
If the recursion has to stops at the dth recursive call, then $ \alpha^d n \le 1 $, that log on both side we get
$ d = -\frac{\log n}{\log \alpha} $.
what do you mean by both sides ?
ReplyDeleteSorry, the original post has a typo, it is corrected now.
DeleteWhen I said both side, I mean both side of the inequality.
I'm completely lost with this solution. Would it possible to write it out in more detail?
ReplyDeleteIt would be easier to interpret if we are talking about exact numbers, instead of variables.
DeleteLet's say we are tossing away (1 - a) = 90% of the numbers per recursion, and you have n = 10000 numbers to begin with.
You used one iteration to reduce the number to 1000
You used one iteration to reduce the number to 100
You used one iteration to reduce the number to 10
You used one iteration to reduce the number to 1
And you stop.
The number of iteration is basically the number of times you need to divide to get to 1, which is the logarithm.