Recurrence formula for Divide and Conquer algorithms - wrong?
I'm currently studying recurrences for divide and conquer algorithms (CLRS chapter 4) and I am struggling to understand a slight change that was made to the latest (4th) edition of the book.
The recurrence relation is defined T(n) = a*T(n/b) + f(n), which resolves to the following:
T(n) = Θ(n^log(a, b) + ∑j=0→log(n,b): a^j * f(n/b^j)
CLRS Ch. 4 Recursion Tree Solution
In the previous version of the book and a lot of places I see online, the limit to ∑ is instead log(n,b)-1, which makes sense since you only include the combine cost f(n) for every level except the last. But now the sum just log(n,2), which considering j starts at 0 and ends at log(n,2), which means f(n) is included for all levels, including leaves. He also changed the definition of a tree's height to be log(n,b) + 1 (which now includes the root) whereas it used to be just log(n,b).
Can somebody explain why these changes were made? I must be misunderstanding something here.
For instance, for a binary tree with just 2 elements with recurrence defined as T(1) = c1 and T(n) = 2T(n/2) + n(c2) where c1 and c2 are constants, I get T(2) = 2(c1) + 2(c2). If I use the solution formula, I get T(2) = 2(c1) + 4(c2) because of the extra sum so the math does not match.
- 1
- 1