I'm reading Algorithms Illuminated: Part 1, and problem 5.3 states:
Let ⍺ be some constant, independent of the input array length n, strictly between 0 and 1/2. Assume you achieve the approximately balanced splits from the preceding problem in every recursive call - so whenever a recursive call is given an array of length k, each of its two recursive calls is passed a subarray with length between ⍺k and (1 - ⍺)k. How many successive recursive calls can occur before triggering the base case? Equivalently, which levels of the algorithm’s 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. [Hint: The formula that relates logarithmic functions with different bases is log n = ln n]
Answer choices:
- -log(n)/log(⍺) <= d <= -log(n)/log(1 - ⍺)
- 0 <= d <= -log(n)/log(⍺)
- -log(n)/log(1 - ⍺) <= d <= -log(n)/log(⍺)
- -log(n)/log(1 - 2⍺) <= d <= -log(n)/log(1 - ⍺)
My analysis:
If ⍺ < 1/2, then 1 - ⍺ > ⍺, thus the branch with subarray length (1 - ⍺)n will have greater recursion depth.
n / (1 - ⍺)^d = 1
Taking log[base(1 - ⍺)] on both sides
log[base(1 - ⍺)](n) = d
By log rule
d = log(n)/log(1 - ⍺)
The best case should be log(n)/log(⍺), thus answer 1 seems to be correct. However, I'm confused by the minus signs; I don't understand how can the height of a recursion tree be negative. Also, I'd like someone to validate my analysis as shown above.
Any ideas?
Your analysis has a small bug.
The correct equation will be n * (1 - ⍺) ^ d = 1 rather than n / (1 - ⍺) ^ d = 1.
This adds the negative sign you are looking for.
Remember that both ⍺ and (1 - ⍺) are less than 1. So, there logarithms are negative. Adding one more negative symbol on that results in an overall positive value for minimum and maximum depth.