Problem:
Now assume that you achieve the approximately balanced splits above in every recursive call --- that is, assume that whenever a recursive call is given an array of length k, then each of its two recursive calls is passed a subarray with length between $ \alpha k $ and $ (1 - \alpha) k$ (where $ 0 < \alpha < .5 $). How many recursive calls can occur before you hit the base case, as a function of $ \alpha $ and the length n of the original input? Equivalently, which levels of the recursion tree can contain leaves? Express your answer as a range of possible numbers $ d $, from the minimum to the maximum number of recursive calls that might be needed. [The minimum occurs when you always recurse on the smaller side; the maximum when you always recurse on the bigger side.]
Solution:
The smallest $ d $ occurs when we always recurse on the smaller side, therefore $ \alpha^d n = 1 $, or in other words,
$ \begin{eqnarray*} \log(\alpha^d n) = 0 \\ d\log(\alpha) +\log(n) = 0 \\ d = -\frac{\log n}{\log \alpha} \end{eqnarray*} $
Similarly, the largest $ d $ occurs when we always recurse on the larger side, therefore $ (1 - \alpha)^dn = 1 $, we get a similar upper bound.
The answer is now $ -\frac{\log n}{\log \alpha} \le d \le -\frac{\log n}{\log (1 - \alpha)} $
Now assume that you achieve the approximately balanced splits above in every recursive call --- that is, assume that whenever a recursive call is given an array of length k, then each of its two recursive calls is passed a subarray with length between $ \alpha k $ and $ (1 - \alpha) k$ (where $ 0 < \alpha < .5 $). How many recursive calls can occur before you hit the base case, as a function of $ \alpha $ and the length n of the original input? Equivalently, which levels of the recursion tree can contain leaves? Express your answer as a range of possible numbers $ d $, from the minimum to the maximum number of recursive calls that might be needed. [The minimum occurs when you always recurse on the smaller side; the maximum when you always recurse on the bigger side.]
Solution:
The smallest $ d $ occurs when we always recurse on the smaller side, therefore $ \alpha^d n = 1 $, or in other words,
$ \begin{eqnarray*} \log(\alpha^d n) = 0 \\ d\log(\alpha) +\log(n) = 0 \\ d = -\frac{\log n}{\log \alpha} \end{eqnarray*} $
Similarly, the largest $ d $ occurs when we always recurse on the larger side, therefore $ (1 - \alpha)^dn = 1 $, we get a similar upper bound.
The answer is now $ -\frac{\log n}{\log \alpha} \le d \le -\frac{\log n}{\log (1 - \alpha)} $
how did you get α^d * n=1 ?
ReplyDelete