Algorithms: Design and Analysis, Part 1 - Problem Set 2 - Question 4

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)}$